Maximum Shortest Path After Road Copying

Syrup is a turtle living in a town containing \(N\) locations and \(M\) bidirectional roads. The locations are numbered from \(1\) to \(N\) and the roads from \(1\) to \(M\). The \(i\)-th road directly connects location \(A_i\) and \(B_i\) with length \(W_i\), and all locations are connected (directly or indirectly) by these roads. Moreover, no two roads share the same pair of endpoints.

The townspeople ranked the roads by aesthetic appeal such that a road with a larger index is more aesthetic. They plan to copy a more aesthetic road onto a less aesthetic road. More precisely, if road \(j\) is copied to road \(i\) (with \(i < j\)), then the length of road \(i\) becomes \(W_i+W_j\), while all other attributes remain the same.

Syrup usually travels from his home at location \(N\) to the main square located at \(1\). He is curious: after performing exactly one valid copy operation, what is the maximum possible value of the shortest path distance from location \(1\) to location \(N</strong>?

Note: If a road is not used in the current shortest path, increasing its length will not affect the distance. Therefore, the optimal copy operation is one that forces the traveler to take a longer detour.

Input constraints and details are provided below.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of locations and roads, respectively.

Each of the following \(M\) lines contains three integers \(A_i\), \(B_i\), and \(W_i\) representing a bidirectional road connecting locations \(A_i\) and \(B_i\) with length \(W_i\). The roads are given in increasing order of their indices (from 1 to \(M\)), which also represents their increasing aesthetic appeal.

outputFormat

Output a single integer: the maximum possible shortest path distance from location \(1\) to location \(N\) after applying exactly one valid copy operation.

sample

3 3
1 2 5
2 3 5
1 3 10

10