ccf#NOI2007A. 社交网络 (Social Network)

社交网络 (Social Network)

Description

There are nn individuals in a social network, and there are different relationships between people. We represent this relational network as an undirected graph with nn nodes. If two different people know each other, we connect an undirected edge between the corresponding nodes and assign a positive weight cc, the smaller the cc, 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 ss and tt. Note that other nodes on the shortest path have a certain degree of importance for the connection between ss and tt. We can measure the importance of the node in the social network by counting the number of shortest paths passing through a node vv. Note that there may be multiple shortest paths between two nodes AA and BB.

We modify the definition of importance as follows: Let Cs,tC_{s,t} represent the number of different shortest paths from ss to tt, Cs,t(v)C_{s,t}(v) represents the number of shortest paths from ss to tt passing through vv; 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 nn and mm 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 11 to nn.

In the next mm lines, each line contains three integers a,b,ca, b, c to describe an undirected edge connecting nodes aa and bb with a weight of cc.

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 nn lines, one real number per line, accurate to 33 digits after the decimal point. The real number in row ii indicates the importance of node ii 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%50\% data, n10,m45n\le10,m\le45.
For 100%100\% data, n100,m4500n\le100,m\le4500, the weight of any edge is a positive integer cc where 1c10001\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 101010^{10}.