Roadblock

Every morning, Farmer John (FJ) walks across his farm from his house to the barn. The farm has $N$ fields ($1 \le N \le 100$) connected by $M$ bidirectional paths ($1 \le M \le 10{,}000$), each with a positive length. FJ's house is in field $1$ and the barn is in field $N$. No two fields are joined by more than one path, and every field is reachable from every other field. Whenever FJ travels, he always takes a route whose total length is minimum.

FJ's mischievous cows want to disrupt his morning walk. They will pile hay bales on exactly one of the $M$ paths, doubling that path's length. The cows want to choose the path so as to maximize the increase in the length of FJ's shortest route from the house to the barn. Determine the largest increase they can cause.

• Line 1: Two space-separated integers $N$ and $M$.
• Lines $2 \dots M+1$: Line $j+1$ describes the $j$-th bidirectional path with three space-separated integers $A_j$, $B_j$, $L_j$. Fields $A_j$ and $B_j$ (each in $1 \dots N$) are joined by a path of length $L_j$ ($1 \le L_j \le 1{,}000{,}000$).

• Line 1: The maximum possible increase in the length of FJ's shortest route from field $1$ to field $N$ that can be achieved by doubling the length of a single path.

In the sample there are $5$ fields and $7$ paths. Initially the shortest route from the house (field $1$) to the barn (field $5$) is $1 \to 3 \to 4 \to 5$ with total length $1 + 3 + 2 = 6$.

If the cows double the length of the path between fields $3$ and $4$ (from $3$ to $6$), FJ's shortest route becomes $1 \to 3 \to 5$ with total length $1 + 7 = 8$, which is $2$ longer than before. No single path can force a larger increase, so the answer is $2$.