6495: 【模板】Dijkstra

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:31 Solved:7

Description

某个地区有  座火车站和  条单向铁路,每条铁路都连接着两座火车站。
每座火车站都有一个自己的编号,分别为 1
其中,中央车站的编号为 1
求从中央车站出发到每座火车站的最短距离是多少。

Input

第一行包含两个正整数  和 
第二行开始的  行,每行包含三个正整数 ,, ,表示从编号  的站点出发 到编号  的站点,存在一条长度为  的铁路。

Output

一行,共  个数字,分别表示从中央车站出发到编号 1 的车站的最短距离,单个空格隔开,如无法到达则输出 1

Sample Input Copy

3 3
1 2 1
1 3 5
2 3 2

Sample Output Copy

0 1 3

HINT

数据范围:
13×105,1106,1,,0109