Description

Every morning, FJ walks from his house across the farm to the barn. The farm consists of $N$ fields connected by $M$ bidirectional roads, each with a certain length. FJ’s house is at field $1$, and the barn is at field $N$. No two fields are connected by multiple roads, and the graph is connected. Whenever FJ travels between fields, he always takes a path with the minimum total length.

FJ’s cows, up to no good as always, decide to disrupt his morning routine. They place a stack of hay bales on one of the $M$ roads, doubling that road’s length. The cows want to choose a road to maximize the increase in FJ’s shortest path distance from home to the barn. They ask you to compute and report this maximum increase.

Input Format

Line $1$: two integers $N, M$.

Lines $2$ to $M+1$: the $(i+1)$-th line contains three integers $A_i, B_i, L_i$. $A_i$ and $B_i$ are the indices of the fields connected by road $i$, and $L_i$ is the length of that road.

Output Format

A single integer: the maximum increase obtained by doubling exactly one road.

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

Hint

Sample explanation: If the length of the road between $3$ and $4$ is doubled, the shortest path changes from $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ to $1 \rightarrow 3 \rightarrow 5$.

Constraints:

• For $30\%$ of the testdata, $N \le 70$, $M \le 1{,}500$.
• For $100\%$ of the testdata, $1 \le N \le 100$, $1 \le M \le 5{,}000$, $1 \le L_i \le 1{,}000{,}000$.

Translated by ChatGPT 5