题目描述

有 n 个城市，m 条单向公路，每条公路都有一个非负的通行时间。请你从城市 1 出发，计算到所有城市的最短时间。

格式

输入

第一行包含两个整数 n 和 m（0 ≤ n ≤ 100）。 接下来 m 行，每行包含三个整数 u、v、w，表示从城市 u 到城市 v 有一条通行时间为 w 的单向公路（0 ≤ w ≤ 1000）。

注意：城市编号从 1 开始。

输出

使用 Dijkstra 算法计算从城市 1 到所有城市的最短路径。 按城市编号从 1 到 n 的顺序输出最短距离，城市之间用空格分隔。

样例

4 5
1 2 2
1 3 5
2 3 1
3 4 2
1 4 1005

0 2 3 5