6495: 【模板】Dijkstra
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:31
Solved:7
Description
某个地区有 座火车站和 条单向铁路,每条铁路都连接着两座火车站。
每座火车站都有一个自己的编号,分别为 。
其中,中央车站的编号为 。
求从中央车站出发到每座火车站的最短距离是多少。
Input
第一行包含两个正整数 和 。
第二行开始的 行,每行包含三个正整数 ,表示从编号 的站点出发 到编号 的站点,存在一条长度为 的铁路。
第二行开始的 行,每行包含三个正整数 ,表示从编号 的站点出发 到编号 的站点,存在一条长度为 的铁路。
Output
一行,共 个数字,分别表示从中央车站出发到编号 的车站的最短距离,单个空格隔开,如无法到达则输出 。
Sample Input Copy
3 3
1 2 1
1 3 5
2 3 2
Sample Output Copy
0 1 3
HINT
数据范围: