E :: Hubs

Time Limit: 3 Seconds    Memory Limit: 65536 KB

As Bob is forgetful, he has a strange plan of driving around the city which reduces the number of routes he must memorize. He selects two distinct locations as hubs (H1 and H2) and partitions other locations into two groups. One group is assigned to H1 while the other is assigned to H2. He then memorizes the shortest route from each location to the hub associated with. If he wants to drive from A to B, he first drives from A to the hub associated with A, then to the other hub (if A and B are not in the same group), and then to B along the shortest route. Note that Bob always drives to hubs even if he visits the destination several times on the path. You should help Bob to find the best two hubs and the best partitioning which minimize the average distance of the trips between any two locations.

Input

The input contains several test cases. The input of each test case is a weighted undirected graph which models the city map. The first line contains two numbers 2 ≤ n ≤ 100, 1 ≤ m ≤ 1000 which are the number of vertices (locations) and the number of edges (streets), respectively.  Each of the next m line describe one edge of the graph with three numbers a, b and d where  1 ≤ a ≤ n, 1 ≤ b ≤ n are location ids and 1 ≤ d ≤ 1000 is the length of the street connecting  a to b (all streets are bidirectional). There may be more than one street between a pair of locations, and a street may start and end at the same location. You may assume there exists a path between any two locations. The input terminates with 0 0.

Output

For each test case, output the minimum average distance of the trips between any two distinct locations with exactly two digits after the decimal point.

Sample Input

3 2
1 2 40
2 3 20
5 5
1 2 2
2 3 3
2 4 3
3 4 5
3 5 1
0 0

Sample Output

40.00
4.20
Submit

Source: 10th Iran Nationwide Internet Contest