Ferries

Time limit2sMemory limit512 MB

Summary

Captains at each island reassign fixed ferry fares among destinations to maximize the cheapest fare from island 1 to island N.

Level: Hard8 of 10
Topics: Shortest path, Greedy, Sorting, Game theory
Solved: No attempts yet

Problem

Kang the penguin lives on a group of $N$ Antarctic islands numbered $1$ to $N$ . His house is on island $1$ . He has a cold today, so he wants to visit the veterinarian who works on island $N$ .

He would normally swim, but with the cold he plans to take ferries instead. There are $M$ ferries, numbered $1$ to $M$ . Ferry $i$ carries passengers from island $A_i$ to island $B_i$ for $C_i$ dollars, and it runs in that direction only. At most one ferry runs from one island to another island, and a ferry may charge $0$ dollars. Kang wants to reach island $N$ as cheaply as possible.

Unfortunately for the penguin, the captains have started a money making scheme today. They know Kang plans to ride from island $1$ to island $N$ , so they agreed to make his trip as expensive as they can. Captains whose ferries depart from the same island may swap destinations among themselves. Their contracts fix the fare of each ferry, so a fare stays with its ferry even after its destination changes. Suppose ferries $1$ , $2$ and $3$ all depart from island $1$ , they go to islands $2$ , $3$ and $4$ , and they charge $10$ , $20$ and $30$ dollars. The captains of ferry $1$ and ferry $2$ may trade destinations, after which ferry $1$ goes to island $3$ and still charges $10$ dollars, while ferry $2$ goes to island $2$ and still charges $20$ dollars.

The captains announce the final destinations before Kang boards any ferry, and they cannot change them afterwards. Kang knows what the captains are planning, but he does not know the destinations before he leaves his house. He wants the smallest amount of money that is certain to be enough for the trip. In other words, find the cost of Kang's cheapest route to island $N$ when the captains arrange the destinations so that this cheapest route costs as much as possible.

Input

Your program reads from standard input. The first line contains two integers $N$ and $M$ . Each of the next $M$ lines contains three integers $A_i$ , $B_i$ and $C_i$ , describing one ferry. A route from island $1$ to island $N$ always exists.

Output

Your program writes one integer to standard output, the minimum number of dollars Kang needs to reach his doctor.

Examples4

Example 1
Input
```
4 5
1 2 2
2 4 2
1 3 10
3 4 7
1 4 7
```
Expected output
```
9
```
Example 2
Input
```
2 1
1 2 5
```
Expected output
```
5
```
Example 3
Input
```
4 3
1 2 0
2 3 0
3 4 0
```
Expected output
```
0
```
Example 4
Input
```
3 2
1 2 1
1 3 100
```
Expected output
```
100
```