Roadblock

Every morning FJ wakes up and walks across the farm from his house to the barn. The farm is a collection of $N$ fields ($1 \le N \le 250$) connected by $M$ bidirectional pathways ($1 \le M \le 25{,}000$), each with a length. FJ's house is in field 1 and the barn is in field $N$. No pair of fields is joined by more than one pathway, and any field can be reached from any other field along some sequence of pathways. When FJ travels from one field to another he always picks a route whose total length is minimum.

FJ's cows, up to no good as always, have decided to interfere with his morning routine. They will pile hay bales on exactly one of the $M$ pathways, doubling that pathway's length. The cows pick the pathway to block so that FJ's distance from the house to the barn grows as much as possible. Work out how much longer they can make his route.

• Line 1: two space separated integers $N$ and $M$.
• Lines 2 to $1+M$: line $j+1$ describes the $j$th bidirectional pathway with three space separated integers $A_j$, $B_j$, $L_j$. $A_j$ and $B_j$ are indices in the range $1$ to $N$ naming the two fields the pathway joins, and $L_j$ is the length of the pathway, in the range $1$ to $1{,}000{,}000$.

• Line 1: the maximum possible increase in the total length of FJ's shortest route that doubling the length of a single pathway can produce.