You are given a weighted undirected graph with numVertices vertices, indexed 0 to numVertices - 1.
The graph has numEdges edges, each with a source, destination and cost.

You have to find the minimum cost to travel from the vertex indexed 0 to each of the vertexes in the graph.

Use Dijkstra's algorithm to calculate the cost.

Example

numVertices: 7
numEdges: 8
Edges: [[0, 1, 2], [0, 3, 3], [0, 6, 4], [1, 2, 3], [1, 4, 2], [3, 4, 5], [4, 5, 7], [4, 6, 6]]
Minimum Cost: [0, 2, 5, 3, 4, 11, 4]

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains two space-separated integers numVertices and numEdges.
• The next numEdges lines descibes the edges of the graph with three space-separated integers - source, destination and weight.

Output Format

For each test case, the output has one line with space-separated values for the minimum cost for each vertex.

Sample Input

4
7 8
0 1 2
0 3 3
0 6 4
1 2 3
1 4 2
3 4 5
4 5 7
4 6 6
3 3
0 1 2
1 2 3
0 2 4
3 2
0 1 2
1 2 3
1 1
0 0 2

Expected Output

0 2 5 3 4 11 4
0 2 4
0 2 5
0

Constraints

1 <= T <= 20
1 <= numVertices <= 500
0 <= numEdges <= 100000
1 <= cost <= 100