The internet connection between Teemu and Taina has had problems lately. Before more investigation on the subject, Teemu decided to find out the theoretical maximum rate at which he can send data to Taina.

Can you help Teemu to calculate the maximum rate?

Input

The first line of the input has two integers n and m: the number of computers and number of connections in the network. Computers are numbered 1,2,\ldots,n. Computer 1 is owned by Teemu and computer n by Taina.

After the first line m lines follow, each of which describe one connection between computers. Each line has three integers a, b and c. This means that computer a can send data to computer b at a rate of c bytes/s. There is at most one connection from computer a to b and no connection connects a computer to itself.

Output

Your program should print one integer: the maximum rate (bytes/s) at which Teemu can send data to Taina.

Limits

• 2 \le n \le 100
• 0 \le m \le 1000
• 1 \le a, b \le n
• 1 \le c \le 10^9

Examples

Input:

4 5
1 2 2
1 3 5
2 4 3
3 2 2
3 4 1

Output:

4