jhljx水水的最短路径

Problem Description

jhljx是一只路痴，一天他不幸坠入一个迷宫中，他灰常想从迷宫中逃出去。
迷宫可以看成一个图，总共有n个节点，jhljx位于第1个节点，他想走最短的路逃出这个迷宫，迷宫节点之间由无向的道路相连接。
这个问题对于聪明的你来说肯定很简单，请你帮帮他吧~

Input

输入多组测试数据。 对于每组测试数据，第一行为两个正整数n（1<=n<=100000），m（1<=m<=1000000），分别表示迷宫中节点的个数，道路的条数。节点编号从1到n。
下面m行为道路的信息。
每一行有三个数x，y，k，从x(y)节点走到y(x)节点之间需要花费k单位时间。（1<=k<=1000）

Output

输出jhljx除入口外其他任意节点逃出迷宫的最短时间，如果无法从该节点逃出，则输出-1。（按照从2~n的顺序输出每个节点的最短时间）

Sample Input

3 2
1 2 5
1 3 4

Sample Output

5 4

Hint

• 为了防止trick较多，数据中不存在重边，不存在自环，边权都大于0
• Dijkstra+heap / SPFA is needed