题目描述

一个无向带权简单连通图，点集记为 V。V 中有 n 个点，编号为 1 ~ n。假设起点为 i，终点为 j，从 i 到 j 的最短路条数记为 $T_{i→j}$。对于一个点 k （k≠i 且 k≠j），从 i 到 j 的最短路中经过 k 的路径条数记为 $S_{i→k→j}$。则 k 点的重要度定义为

$$\sum_{i∈V,j∈V,i < j,i≠k,j≠k} \frac {S_{i→k→j}}{T_{i→j}} $$

求每一个点的重要度。按编号顺序从小到大输出，每行一个，保留 3 位小数。

输入格式

第一行：两个整数 $n$ 和 $m$ ，表示点数和边数。

接下来 $m$ 行：每行 3 个整数 $u, v, w$ 表示 $u$ 和 $v$ 之间有一条权值为 $w$ 的无向边。

输出格式

共 $n$ 行，每行一个实数，保留 3 位小数。

样例输入

3 3
1 2 1
2 3 2
3 1 3

样例输出

0.000
0.500
0.000

数据范围

$50\%$ 的数据： $n ≤ 10, m ≤ 50$。

$100\%$ 的数据： $n ≤ 100, m ≤ 5000, 1 ≤ w ≤ 1000$。数据保证中间运算结果 $< 2^{63}$ 。