题目描述

向 Byteland 的国王 Bitolomew 致敬！

国王 Bitolomew 认为 Byteland 是一个独一无二的国家。

它太小了，它所有的市民（包括国外）都只在农场或工厂之一工作，其中农场和工厂是两个不同的城市。

因此每天早晨，每个城市的居民都在去这两个城市的路上通行。

Byteland 的交通网络包括一些连接两个不同城市的无向的道路，道路不会连向国家之外的城市（但是隧道和桥可能会这样）。

两个城市间可能存在多条无向的道路。保证农场和工厂与所有城市连通。

几个月前，为了改善交通状况，国王 Bitolomew 出台了过路费的政策，需要每个市民每次在通过相应道路时支付固定的费用。

Bitolomew 希望这能引导市民重新考虑他们的上班路线，从而使得交通更加均匀畅通。

国王的点子被他的谏者证明是不够完美的。

每个 Byteland 的市民现在都开始走起了最便宜的上班路线。

国王 Bitolomew 完全没想到会出现这种情况，然而过路费带来的收入着实提高了国家财政的收入。

事实上，国王现在的经济状况实在是太好了，所以他准备在一个新的首都建一个新的城堡。

新的首都必须和一些其他的城市通过无向的道路相连，这样才能从新首都到达每个城市。

新建的道路可以设定非负的过路费（特别地，这里的过路费可以不是整数）。

国王 Bitolomew 真的很讨厌车辆路过他的城堡所产生的噪声。

他希望通过合理设定新道路的过路费使得从任意除了新首都之外的城市 $v$ 到农场或工厂都不会经过新首都（注意这里 $v$ 还包括农场和工厂）。

另外，由于国王也要交过路费，所以他希望最小化从新首都到其他每个城市的平均过路费。

请你帮助国王计算一下最小可能的平均值是多少吧。

输入格式

第一行一个正整数 $T$，表示有 $T$ 组数据。

每组数据第一行两个正整数 $n$ 和 $m$，表示 Byteland 有 $n$ 个城市和 $m$ 条道路。

接下来 $m$ 行，每行三个整数表示城市 $u$ 和城市 $v$ 之间有一条过路费为 $c$ 的道路。

两个城市间可能存在多条无向的道路。

农场所在的城市标号为 $1$，工厂所在的城市标号为 $2$。

输出格式

对于每组数据输出一行，最小可能的从新首都到其他点所需过路费的平均值。

你的答案应该和标准答案误差不超过 $10^{-8}$。

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

1.833333333333 

数据规模与约定

对于 $100\%$ 的数据满足，$2 \le n \le 3 \times 10^5$，$1 \le m \le 3 \times 10^5$， $1 \le u,v \le n$，$u \neq v$，$0 \le c \le 10^6$。