Test1.C

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个有n个顶点,m条边的带权有向图。求从顶点1到其他所有点的最短路径。(n<=1000, m<=10000)。
 

Input

第一行为一个整数T,代表测试数据的组数。
每组测试数据的开头包含两个整数n,m。分别代表顶点数和边数。
以下m行每行有3个整数x,y,z,代表从x到y有一条权值为z的边。
(x,y,z <= 1000)

Output

每组数据的输出包含n行,分别代表从顶点1到顶点1,2,3,4,5....,n的最短路径。如果从1到某个顶点没有路径,则输出-1。

Sample Input

2
3 3
1 2 1
2 3 1
1 3 1
2 0

Sample Output

0
1
1
0
-1

Hint

 

Source

polla