Description

There are $n$ individuals in a social network, and there are different relationships between people. We represent this relational network as an undirected graph with $n$ nodes. If two different people know each other, we connect an undirected edge between the corresponding nodes and assign a positive weight $c$, the smaller the $c$, the closer the relationship between the two people. We can use the shortest path length between the corresponding nodes to measure the closeness of the relationship between two people $s$ and $t$. Note that other nodes on the shortest path have a certain degree of importance for the connection between $s$ and $t$. We can measure the importance of the node in the social network by counting the number of shortest paths passing through a node $v$. Note that there may be multiple shortest paths between two nodes $A$ and $B$.

We modify the definition of importance as follows: Let $C_{s,t}$ represent the number of different shortest paths from $s$ to $t$, $C_{s,t}(v)$ represents the number of shortest paths from $s$ to $t$ passing through $v$; then it is defined as:

$$I(v) =\sum_{s \neq v, t \neq v}\frac{C_{s,t}(v)}{C_{s,t}} $$

It is guaranteed there is a shortest path of finite length between any two nodes. Now given such a weighted undirected graph describing a social network, please find the importance of each node.

Input Format

There are two integers $n$ and $m$ in the first line of input, which represent the number of nodes and the number of undirected edges in the social network.

In the undirected graph, we number all nodes from $1$ to $n$.

In the next $m$ lines, each line contains three integers $a, b, c$ to describe an undirected edge connecting nodes $a$ and $b$ with a weight of $c$.

Note that there is at most one undirected edge connected between any two nodes, and there will be no self-loop in the undirected graph.

Output Format

The output consists of $n$ lines, one real number per line, accurate to $3$ digits after the decimal point. The real number in row $i$ indicates the importance of node $i$ in the social network.

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

1.000
1.000
1.000
1.000

Constraints

For $50\%$ data, $n\le10,m\le45$.
For $100\%$ data, $n\le100,m\le4500$, the weight of any edge is a positive integer $c$ where $1\le c \le 1000$.
It is guaranteed that the undirected graph is connected and the number of shortest paths between any two nodes doesn't exceed $10^{10}$.