18906번 - Minimal Variance Tree 스페셜 저지다국어

문제

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}$.

제한

힌트