题目描述

在社交网络（social network）的研究中，我们常常使用图论概念去解释一些社会现象。

不妨看这样的一个问题。在一个社交圈子里有 \(n\) 个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个 \(n\) 个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值 \(c\)，\(c\) 越小，表示两个人之间的关系越密切。

我们可以用对应结点之间的最短路长度来衡量两个人 \(s\) 和 \(t\) 之间的关系密切程度，注意到最短径上的其他结点为 \(s\) 和 \(t\) 的联系提供了某种方面上的便利，即这些结点对于\(s\) 和 \(t\) 之间的联系有一定的重要程度。我们通过统计经过一个结点 \(v\) 的最短路径的数目来衡量该结点在社交网络中的重要程度，

考虑到两个结点 \(A\) 和 \(B\) 之间可能会有多条最短路径。我们修改重要程度的定义如下：

令 \(C_{s,t}\) 表示从 \(s\) 到 \(t\) 的不同的最短路的数目，\(C_{s,t}(v)\) 表示经过 \(v\) 的从 \(s\) 到 \(t\) 的最短路的数目；则定义

\[ I(v) = \sum_{s \ne v,t \ne v} \frac{C_{s,t}(v)}{C_{s,t}}\]

为结点 \(v\) 在社交网络中的重要程度。

为了使 \(I(v)\) 和 \(C_{s,t}(v)\)有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间，都有一条有限长度的最短路径。

现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。

输入

第一行，有两个整数，\(n\) 和 \(m\)，表示社交网络中结点和无向边的数目。在无向图中，我们将所有结点从 \(1\) 到 \(n\) 进行编号。

接下来\(m\)行，每行用三个整数 \(a,b,c\) 描述一条连接结点 \(a\) 和 \(b\)，权值为 \(c\) 的无向边。注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

输出

包括 \(n\) 行，每行一个实数，精确到小数点后3位。第 \(i\) 行的实数表示结点 \(i\) 在社交网络中的重要程度。

样例

输入

4 4
1 2 1
2 3 1
3 4 1
4 1 1

输出

1.000
1.000
1.000
1.000

解释

社交网络如下图所示。

对于 \(1\) 号结点而言，只有 \(2\) 号到 \(4\) 号结点和 \(4\) 号到 \(2\) 号结点的最短路经过 \(1\) 号结点，而 \(2\) 号结点和 \(4\) 号结点之间的最短路又有 \(2\) 条。因而根据定义，\(1\) 号结点的重要程度计算为 \(frac{1}{2} + frac{1}{2} = 1\)。由于图的对称性，其他三个结点的重要程度也都是 \(1\)。

评分方法

本题没有部分分，仅当你的程序计算得出的各个结点的重要程度与标准输出相差不超过 \(0.001\) 时，才能得到测试点的满分，否则不得分。

数据范围限制

\(50\%\) 的数据中：\(n \leq 10\)，\(m \leq 45\)
\(100\%\) 的数据中：\(n \leq 100\)，\(m \leq 4500\)，任意一条边的权值 \(c\) 是正整数，满足：\(1 \leq c \leq 1000\)。

所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过 \(10^{10}\)。

来源

NOI2007 D1T1