Bitolomew 国王万岁！

Bitolomew 国王认为 Byteland 是一个相当独特的国家。它非常小，所有的公民（国王除外）都在农场或工厂工作，这两个地方位于两个不同的城市。因此，每天早上，每个城市的居民都会在拥堵的交通中通勤到这两个城市。

Byteland 的道路网络由连接不同城市对的无向道路组成。道路在城市之外不会交叉（但可能存在隧道和桥梁）。两个城市之间可能存在多条直接道路。农场和工厂从所有城市都是可达的。

几个月前，为了改善交通状况，Bitolomew 国王在每条道路上都设置了通行费，要求公民每次使用道路时支付固定的（每条路）费用。Bitolomew 希望支付费用的前景能促使一些公民重新考虑他们的路线，从而使交通分布更加均匀。

正如他的顾问所说，国王的想法并不完美。现在，Byteland 的每一位公民都使用最便宜的路线去上班！Bitolomew 国王对此并不太担心，因为通行费收入确实改善了王国的预算。事实上，国王现在的财政状况非常好，他计划为自己建造一个带有新城堡的新首都。这个新首都应该通过直接道路与其它一些城市相连，以便从它出发可以到达每一个城市。新创建的道路可以分配任何非负的通行费（特别是，通行费不必是整数）。

Bitolomew 国王非常讨厌经过他城堡的汽车所产生的噪音。他希望为从新首都出发的新道路设置通行费，使得对于除首都之外的任何城市 $v$，都存在从 $v$ 到农场和工厂的最便宜路径，且这些路径不经过首都（注意，这里的 $v$ 也可以是拥有农场或工厂的城市）。另一方面，由于国王本人也需要支付通行费，他希望最小化从新首都到其它每个城市的平均最便宜路径成本。

请帮助国王确定该最小可能成本。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例以两个整数 $n, m$ ($2 \le n \le 10^5, 1 \le m \le 3 \cdot 10^5$) 开头，分别表示 Byteland 的城市数量和道路数量。接下来的 $m$ 行描述了道路。每条道路由三个整数 $u, v, c$ ($1 \le u, v \le n, u \neq v, 0 \le c \le 10^6$) 描述，表示由该道路连接的两个城市的索引以及国王为该道路设置的通行费。任意两个城市之间可能存在多条道路。

拥有农场和工厂的城市索引分别为 1 和 2。

输出格式

按输入中出现的顺序打印测试用例的答案。对于每个测试用例，打印一行，包含从新首都到达其它城市的最便宜路径的最小可能平均成本。如果你的答案的绝对误差或相对误差低于 $10^{-8}$，则将被接受。

样例

输入 1

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

输出 1

1.833333333333