Betweenness Centrality in Social Network Graphs

Given a connected weighted undirected graph representing a social network with n vertices and m edges, each edge u-v has a positive weight c (with a smaller value indicating a closer relationship between the two persons), you are to compute the importance of every vertex. The importance I(v) of a vertex v is defined as:

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

where for any two distinct vertices s and t (with s,t \neq v):

• C_s,t is the number of different shortest paths between s and t.
• C_s,t(v) is the number of those shortest paths that pass through vertex v.

This measure is a version of the betweenness centrality used in social network analysis. Note that the graph is guaranteed to be connected so that a shortest path exists between every pair of nodes.

Task: Compute and output I(v) for every vertex v.

inputFormat

The first line contains two integers n and m, representing the number of vertices and edges respectively.

Each of the next m lines contains three positive numbers u, v and w, indicating there is an undirected edge between vertices u and v with weight w.

Vertices are numbered from 1 to n. The graph is connected.

outputFormat

Output n lines. The i-th line should contain the importance I(i) of vertex i as a floating point number. Print the answer with at least 6 decimal places of precision.

sample

3 3
1 2 1
2 3 1
1 3 2

0.000000
0.500000
0.000000

</p>