Distance

A city contains a number of streets connecting several junctions. All the streets are straight line segments connecting two junctions. The walking distance between two points (each either a junction or some intermediate point of a street) in the city is the shortest path from the first point to the second. You are allowed to walk only along the streets. Streets never intersect outside the junctions. Now, your goal is to find the maximal walking distance among any two points in the city.

The input file contains several test cases. Each test case begins with two integers n and m ( 1<=n<=50, 0<=m<=n*(n-1)/2 ), which are the number of junctions and the number of streets. The following m lines each contain 3 integers Xi, Yi and Si ( 0<=Xi,Yi<n, 0<Si<=1000) indicating there is a street connecting junction Xi to Yi and the length is Si.

For each test case, output the maximal walking distance among any two points in the city. Accurate up to 1 decimal places. If there is a point which is separate from some other one, just output -1.

1 0
2 0
2 1
1 0 100
4 3
0 1 1
0 2 2
0 3 3
4 4
0 1 2
1 2 3
2 3 4
3 0 8

0.0
-1
100.0
5.0
8.5

暑期集训队选拔赛（2）