Given an undirected weighted graph {V,E}. Your task to calculate the importance of each node.

The importance of a node v (I(v)) can be defined as follow:

C_s,t is the number of different shortest paths from s to t, C_s,t(v) is the number of different shortest paths from s to t through v.

Input

Multiple test cases, the number of them is given in the very first line.

For each test case:

The first line contains two space-separated integers n(n<=100) and m(m<=4500), the number of nodes in the graph and the number of edges in the graph. The nodes are numbered from 1 to n. m lines follow, each contains 3 integers a, b, c, 1<=a, b<=n, 1<=c<=1000, a!=b, which denotes that there is an undirected edge between node a and node b weighted c. You may assume that there is at most one edge between any pair of nodes, and the number of shortest paths between any pair of nodes is at least 1 and at most 10¹⁰.

Output

For each test case:

Your Output should contains n lines, each contains one single real number, with 3 decimal places after radix point. The number in the ith line denotes the importance of the ith node.

Example

Input:
1
4 4
1 2 1
2 3 1
3 4 1
4 1 1

Output:
1.000
1.000
1.000
1.000