In the study of social networks, we often use graph theory concepts to explain social phenomena.

Consider the following problem. In a social circle, there are $n$ people, and there are varying degrees of relationships between them. We represent this relationship network as an undirected graph with $n$ nodes. If two different people know each other, we connect an undirected edge between their corresponding nodes and assign it a positive weight $c$. A smaller $c$ indicates a closer relationship between the two people.

We can measure the closeness between two people $s$ and $t$ by the length of the shortest path between their corresponding nodes. Note that other nodes on the shortest path provide some convenience for the connection between $s$ and $t$, meaning these nodes have a certain degree of importance for the connection between $s$ and $t$. We can measure the importance of a node in the social network by counting the number of shortest paths that pass through it.

Considering 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}$ be the number of different shortest paths from $s$ to $t$, and $C_{s,t}(v)$ be the number of shortest paths from $s$ to $t$ that pass through $v$. Then, the importance of node $v$ in the social network is defined as:

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

To ensure $I(v)$ and $C_{s,t}(v)$ are meaningful, we assume that the social networks to be processed are connected undirected graphs, meaning there is a shortest path of finite length between any two nodes.

Given such a weighted undirected graph describing a social network, calculate the importance of each node.

Input

The first line of the input file contains two integers, $n$ and $m$, representing the number of nodes and undirected edges in the social network. In the undirected graph, all nodes are numbered from $1$ to $n$.

The next $m$ lines each contain three integers $a, b, c$, describing an undirected edge connecting nodes $a$ and $b$ with weight $c$. Note that there is at most one undirected edge between any two nodes, and there are no self-loops in the undirected graph (i.e., there is no edge where both endpoints are the same node).

Output

The output file contains $n$ lines, each containing a real number, accurate to 3 decimal places. The real number on the $i$-th line represents the importance of node $i$ in the social network.

Examples

Input 1

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

Output 1

1.000
1.000
1.000
1.000

Note

The social network is shown in the figure below.

For node 1, only the shortest paths from node 2 to node 4 and from node 4 to node 2 pass through node 1, and there are 2 shortest paths between node 2 and node 4. Therefore, according to the definition, the importance of node 1 is calculated as $\frac{1}{2} + \frac{1}{2} = 1$. Due to the symmetry of the graph, the importance of the other three nodes is also 1.

Subtasks

There is no partial credit for this problem. You will receive full marks for a test case only if the importance of each node calculated by your program differs from the standard output by no more than $0.001$; otherwise, you will receive no points.

Constraints

• For 50% of the data: $n \le 10, m \le 45$
• For 100% of the data: $n \le 100, m \le 4\,500$, and the weight $c$ of any edge is a positive integer satisfying $1 \le c \le 1\,000$.
• In all data, the given undirected graph is guaranteed to be connected, and the number of shortest paths between any two nodes does not exceed $10^{10}$.