标准差

题号：NC14598
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

对于一张n个点m条边的有向图，边上有边权w_e，你需要找到一条1到n的路径使得经过的边的标准差最小。

x₁,x₂,...,x_k的标准差计算方法如下：

设 $\overline{x}=\frac 1 k\sum x_i$ 。

则标准差 $S=\sqrt{\frac 1 k\sum (x_i-\overline{x})^2}$ 。

note：这条路径不一定要是简单路径。

第一行两个整数n,m。
接下来m行每行三个数u,v,x表示u指向v有一条权为w的边。

 输出一行一个实数，你的答案和标准答案相对误差或者绝对误差不超过10^-6就算正确。

示例1

复制

2 1 1 2 3

复制

20%的数据，n ≤ 10, 0 ≤ w ≤ 300，没有重边。
30%的数据，n ≤ 20, m ≤ 100, 0 ≤ w ≤ 20, u < v。
30%的数据，n ≤ 20, m ≤ 50, 0 ≤ w ≤ 20。
20%的数据，n ≤ 30, m ≤ 100, 0 ≤ w ≤ 100。