说明

国王比特洛缪认为比特国是一个相当独特的国家。它非常小，所有国民（不包括国王）要么在农场工作，要么在工厂工作，这两个工作地点分别位于两个不同的城市。因此，每天早上，每个城市的居民都要经历严重的交通堵塞，通勤到这两个城市。

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

几个月前，为了改善交通状况，国王比特洛缪对每条道路征收通行费，要求市民每次使用道路时支付固定的（每条路）费用。比特洛缪希望付费的前景能迫使一些市民重新考虑他们的路线，从而使交通分布更均匀。

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

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

帮助国王确定这个最小可能的成本。

输入格式

输入的第一行包含测试用例的数量 $T$。随后是每个测试用例的描述：

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

农场和工厂所在城市的编号分别为 $1$ 和 $2$。

输出格式

按照输入中出现的顺序输出每个测试用例的答案。对于每个测试用例，输出一行，包含从新首都到达其他城市的最小可能平均成本。如果答案的绝对误差或相对误差低于 $10^{-8}$，则被视为正确。

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

1.833333333333