Maximizing FJ's Morning Walk Increase

FJ starts his day by walking from his house in field $1$ to the barn in field $N$. The farm consists of $N$ fields connected by $M$ bidirectional roads, each with a positive length. There is a unique route order such that one can travel between any two fields. Every time FJ moves from one field to another, he always takes a route with the minimum total distance.

A mischievous cow decides to disrupt FJ's routine by choosing one road and doubling its length (i.e. replacing a road with length $w$ by one with length $2w$). Note that after this change, FJ will recalculate his route and take the new shortest path from field $1$ to field $N$.

Your task is to compute the maximum possible increase in the shortest path distance from field $1$ to field $N$ that the cow can force, by optimally choosing the road to double.

In mathematical terms, let $d$ be the original shortest distance from $1$ to $N$, and let $d_e$ be the new shortest distance if the length of road $e$ is doubled. You need to output (\max_{e},(d_e-d)).

inputFormat

The first line contains two integers $N$ and $M$, where $N$ represents the number of fields and $M$ represents the number of roads. Each of the following $M$ lines contains three integers $u$, $v$, and $w$, indicating that there is a bidirectional road connecting field $u$ and field $v$ with length $w$. It is guaranteed that no two fields are connected by more than one road and the farm is connected.

outputFormat

Output a single integer: the maximum increase in the shortest path distance from field $1$ to field $N$ after doubling the length of one road.

sample

3 3
1 2 1
2 3 1
1 3 3

1