Problem J
Replacement roads

The city A has $n$ junctions and $m$ bidirectional roads between two junctions. The junctions are labeled from $1$ to $n$. Each road has its own length that is a positive integer. Roads usually become heavily congested in rush hours. Therefore, city council uses a metric called replacement value for each road $(x, y)$ to estimate its connectivity. The replacement value is calculated as follows:

where:

• $f(u,v,x,y)$ is the length of the shortest path from $u$ to $v$ when the $(x,y)$ road is blocked.

• $g(u,v)$ is the length of the shortest path from $u$ to $v$.

Set $r_{xy} = -1$ if there is no path from any $u$ to any $v$ when the road $(x,y)$ is blocked. It is noted that the length of a path from $u$ to $v$ is the sum of all lengths of the roads in this path.

Your task is to find the road that has the maximum replacement value.

Input

The input file consists of following lines:

• The first line contains two integers $n, m$ $(2 \leq n \leq 200, 1 \leq m \leq 2000)$;

• The ${i}^{th}$ line in the following $m$ lines contains three positive integers ${x}_{i}, {y}_{i}, {d}_{i}, (1 \leq {x}_{i}, {y}_{i} \leq n, {d}_{i} \leq 10^6$ for $i = 1, 2,..., m$) - describing a bidirectional road whose endpoints are $x_ i$ and $y_ i$ with distance $d_ i$.

Output

Write in one line $r_{max}$ with absolute error less than $10^{-6}$ that is the highest replacement value of city roads.

5 7
1 2 1
1 3 2
1 4 1
2 3 5
2 5 1
5 3 1
3 4 6

8.000000

3 2
1 2 8
2 3 5

1.000000

2 1
1 2 10

-1.000000