Ant-Elephant War

The animal kingdom map is an undirected weighted graph with N vertices and M roads. The ant kingdom is at vertex 1, and the elephant kingdom is at vertex N. The ant kingdom always travels from vertex 1 to vertex N along a shortest route.

To delay the attack as much as possible, exactly one road will be destroyed. After that road is removed, the ant kingdom again chooses a shortest route from vertex 1 to vertex N.

It is guaranteed that, no matter which single road is destroyed, vertex N is still reachable from vertex 1. Find the maximum possible shortest distance from vertex 1 to vertex N after destroying exactly one road.

The first line contains N and M, the number of vertices and roads. 1 ≤ N ≤ 1000 and 1 ≤ M ≤ N×(N-1)/2.

Each of the next M lines contains three integers x_i, y_i, and z_i. This means there is a road between vertices x_i and y_i, and traveling through it takes z_i time.

There is at most one road between any pair of vertices. All roads are bidirectional, and destroying a road removes it in both directions. 1 ≤ x_i, y_i ≤ N and 1 ≤ z_i ≤ 1000.

Print the maximum possible shortest distance from vertex 1 to vertex N after destroying one suitable road.