Problem G
Average Spanning Tree

Victor works at a company dealing with trees. Unlike most such companies, the one Victor works at does not cut them down. Instead, they create new trees from graphs. For example, some customers might give them a graph and ask for the minimum spanning tree, while others might order steiner trees (only served if they pay a premium). Thanks to countless years of algorithmic research, they have efficient and exact algorithms to produce all sorts of trees. It has gotten to the point that Victor is growing tired of the job, as nothing exciting happens. Because of this, he has decided to spice things up by replacing their minimum spanning tree algorithm with one that samples a spanning tree uniformly at random from the graph (each spanning tree being equally likely). A spanning tree of a graph with $V$ vertices is a subset of its edges of size $V-1$, such that the graph is connected using only these edges.

However, Victor does not want to risk getting fired. In order to evaluate whether anyone is likely to notice the change in algorithm, he wants to measure how good this new algorithm is. The weight of a spanning tree is the sum of the weight of all of its edges. He wants to compute the average weight of a uniformly randomly sampled spanning tree from a given weighted graph (one where each edge has a weight). Unfortunately, his company does not yet have an algorithm for this. Please help Victor compute the average weight of all spanning trees for a given graph.

Input

The first line of input contains the integers $V$ and $E$ ($2 \leq V \leq 50$, $1 \leq E \leq \frac{V(V-1)}{2}$), the number of nodes and edges in the graph.

The following $E$ lines each contain the integers $a,b$ and $w$ ($1 \leq a,b \leq V$, $a \neq b$, $1 \leq w \leq 10^6$), meaning that there is an edge between node $a$ and $b$ with weight $w$. It also holds that there is at most one edge between every pair of nodes.

Output

Print a decimal number: the average weight of a uniformly randomly selected spanning tree. The answer will be accepted if the relative or absolute error of your answer compared to the judge’s is at most $10^{-5}$.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Explanation of sample 1

There are three spanning trees of the sample graph. They have weight $6+4$, $4+9$ and $9+6$, totalling $38$. $\frac{38}{3} \approx 12.667$

3 3
1 2 4
2 3 9
3 1 6

12.666666666666667

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

4.875000000000000