F :: Farm and factory

Time Limit: 10 Seconds    Memory Limit: 131072 KB
Special Judge

All hail Bitolomew, the king of Byteland!

King Bitolomew thinks that Byteland is a rather unique country. It is quite small, and all of its citizens (excluding the king) work either at the farm or at the factory, which are located in two distinct cities. So, every morning, the inhabitants of each city commute to these two cities in great traffic jams.

The road network of Byteland consists of undirected roads joining pairs of distinct cities. The roads do not cross outside cities (but tunnels and bridges may occur). There may exist multiple direct roads between two cities. The farm and the factory are both reachable from all cities.

A few months ago, in an attempt to improve the traffic situation, king Bitolomew has introduced tolls on every road, requiring citizens to pay a fixed (per road) amount every time they want to use a road. Bitolomew hoped that the prospect of paying money would force some citizens to reconsider their routes, and thus distribute the traffic more evenly.

The king’s idea turned out to be, as his advisors say, less than perfect. Every citizen of Byteland now uses the cheapest route to commute to work! King Bitolomew is not overly concerned about this, as the income from tolls has really improved the kingdom’s budget. In fact, the king’s finances are now so good that he plans to build himself a new capital with a new
castle in it. This new capital should be connected with some other cities by direct roads, so that every city is reachable from it. The newly created roads can have any non-negative tolls assigned (in particular, the tolls do not have to be integer).

King Bitolomew really dislikes the noise generated by cars passing by his castle. He would like to set the tolls for the new roads going out from his new capital so that for any city v other than the capital there exist cheapest paths from v to both the farm and the factory that do not pass through the capital (note that v here can also be the city with the farm or the factory). On the other hand, since the king is not exempt from the tolls, he would like to minimize the average cost of cheapest paths from the new capital to every other city.

Help the king determine that minimum possible cost.

Input

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:

Each test case starts with two integers n,m (2 <= n <= 10^5, 1 <= m <= 3 · 10^5) denoting the number of cities and the number of roads in Byteland, respectively. The next m lines describe the roads. Each road is described by three integers u, v, c (1 <= u, v <= n, u != v, 0 <= c <= 10^6), denoting the indices of the two cities joined by the road and the toll the king has set for that road. There may be multiple roads between any given pair of cities.

The indices of the cities with the farm and the factory are 1 and 2, respectively.

Output

Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line containing the minimum possible average cost of reaching other cities from the newly created capital. Your answer will be accepted if its absolute or relative error is below 10^−8.

Sample Input

1
3 3
1 2 5
2 3 5
3 1 1

Sample Output

1.833333333333

Submit

Source: Central European Regional Contest 2012