暂无测试数据。

题目描述

放假了，小Z觉得呆在家里特别无聊，
于是决定一个人去游乐园玩。

进入游乐园后，小Z看了看游乐园的地图，
发现可以将游乐园抽象成有 \(n\) 个景点、\(m\) 条道路的无向连通图，
且该图中至多有一个环（即 \(m\) 只可能等于 \(n\) 或者 \(n-1\)）。

小Z现在所在的大门也正好是一个景点。
小Z不知道什么好玩，
于是他决定，从当前位置出发，
每次随机去一个和当前景点有道路相连的景点，
并且同一个景点不去两次（包括起始景点）。

贪玩的小Z会一直游玩，
直到当前景点的相邻景点都已经访问过为止。

小Z所有经过的景点按顺序构成一条非重复路径，
他想知道这条路径的期望长度是多少？

小Z把游乐园的抽象地图画下来带回了家，
可是忘了标哪个点是大门，
他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。
同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

输入

第一行，两个整数 \(n\) 和 \(m\)，分别表示景点数和道路数。
接下来 \(m\) 行，
每行三个整数 \(X_i\),\(Y_i\),\(W_i\)，
分别表示第 \(i\) 条路径的两个景点为 \(X_i,Y_i\) ，路径长 \(W_i\)。
所有景点的编号从 1 至 \(n\)，两个景点之间至多只有一条道路。

输出

一个实数，即路径的期望长度。

样例输入

4 3
1 2 3
2 3 1
3 4 4

样例输出

6.00000000

数据范围限制

来源

NOI2012