Roadblock Inspection

Figure 1 shows a graph of a city, its major locations, and the travel times between them. Each node is a major location, and the number written on a road between two locations is the time, in minutes, needed to travel along that road. The road connecting locations a and b is called road(a, b).

Figure 1

For instance, traveling from location 1 to location 3 through road(1, 2) and road(2, 3) takes 3 minutes. Every road is bidirectional, so road(a, b) and road(b, a) always take the same amount of time.

A suspect enters the city at location 1 and wants to leave as quickly as possible by reaching location N. The police know this and choose exactly one road for an inspection. The suspect avoids that road and still chooses the fastest possible escape route. Depending on which road the police choose, the shortest escape time may become longer than it was with no inspection.

Your task is to compute the maximum escape delay that can be caused by inspecting one road. The conditions are as follows.

1. If two locations are directly connected, there is only one road between them.
2. City locations are numbered with consecutive integers from 1 through N.
3. The suspect always enters at location 1 and must finally reach location N to leave the city.
4. The suspect chooses the fastest route that avoids the inspected road, while the police choose one road to delay the suspect as much as possible.
5. Every road travel time is a positive integer.

Depending on the road network, blocking one road may make it impossible for the suspect to leave the city. In that case the delay is infinite, and you must output -1.

In Figure 1, without any inspection, the suspect can leave the city in 4 minutes. If the police block road(4, 3), the escape time does not increase, so the delay is 0. If they block road(2, 3), the fastest escape time becomes 5 minutes and the delay is 1 minute. If they block road(3, 6), the delay is 2 minutes.

Read the road network and output the maximum integer delay that can be caused by blocking one road. If no delay is possible, output 0. If escape can be made impossible, output -1.

The first line contains two integers N(6 <= N <= 1000), the number of locations, and M(6 <= M <= 5000), the number of roads. Each of the next M lines describes a road(a, b) and its travel time t in the form a b t. Here a < b and 1 <= t <= 10000.

Output one integer: the maximum time by which the police can delay the suspect by blocking one road. If the delay is infinite, output -1.