시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 32 4 3 14.286%

문제

Sophie learned today that the notion  of variance can be extended to edge-weighted trees: given a tree with edges $E$ this is a sum (over  $E$) of squared differences between the weights of the edges and the mean weight of the edges. She was able to come up with a formula for that: if $w_e$ denotes the weight of the edge $e$ then the variance of the tree is

\[\sum_{e \in E} \left( w_e - S_T \right)^2 \mbox{, where } S_T = \sum_{e \in E}  \frac{w_e}{|E|}\enspace .\]

Sophie wonders, whether for a given multigraph she can compute its spanning tree with the  smallest variance. Help her in this task.

입력

First line of the input contains two positive integers $n$ and $m$ $(2 \leq n \leq 10\,000$, $1 \leq m \leq 10\,000)$, denoting the number of vertices and edges of the graph. Each of the following $m$ lines contains three positive integers $a_i$, $b_i$ and $w_i$ $(1 \leq a, b \leq n$, $a \neq b$, $1 \leq w \leq 100\,000)$,  this is the description of the $i$th edge, which connects the vertices $a_i$ and $b_i$ and has the weight $w_i$.

The described graph is connected, it can have many edges between any two vertices, those edges can have different weights.

출력

You should  one real number: minimal value of variance of a spanning tree of the given graph. The answer is accepted if the relative or absolute error is at most $10^{-6}$.

예제 입력 1

4 6
1 2 3
2 3 9
3 4 7
1 3 5
1 3 6
4 1 2

예제 출력 1

4.666666667