1534: 乡村的路
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：51
Solved：29
Description
南坪乡共有n个村庄，实施“畅通工程”后，连接各个村庄的 m条道路都整修得更宽更平整了。现在给你一张连通 n个村庄的交通图g，请你帮助计算出从乡政府所在的村庄1出发到各村庄的最短路。
给你南坪乡连接各个村庄的道路数据。每条道路的数据有3个数x,y,z。表示村庄x到村庄y的距离值z。如下图所示的乡村道路网，其村庄1出发到各村庄的最短路分别为: 1-2=4 ; 1-3=5 ; 1-4=9; 1-5=7; 1-6=8。
Input
输入第一行为两个正整数n与m。n表示村庄个数（村庄编号为 1~n），m表示边的条数。接下来m行，每行有3个数x,y,z。表示村庄x到村庄y的距离值z。
Output
输出一行数据 表示从乡政府所在的村庄1出发依序到各村庄的最短路。数据之间空一格。
Sample Input Copy
6 9
1 2 4
1 3 8
2 3 1
2 5 3
3 4 5
3 6 12
5 4 2
4 6 6
5 6 1
Sample Output Copy
4 5 9 7 8
HINT
2=<n<=20