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