题目描述

给定一个有向图，包含 n 个顶点，编号从 1 到 n，以及 m 条带权边。求从顶点 1 到其余所有顶点的最短路径长度。如果某个顶点不可达，输出 -1。

输入格式

第一行两个整数 n 和 m，表示顶点数和边数。 接下来 m 行，每行三个整数 u, v, w，表示一条从 u 到 v 的有向边，权值为 w。

输出格式

一行 n-1 个整数，分别表示从顶点 1 到顶点 2, 3, ..., n 的最短路径长度。如果不可达，输出 -1。

样例输入

4 5
1 2 2
1 3 5
2 3 1
2 4 6
3 4 1

样例输出

2 3 4

样例解释

• 1→2：直接走边 1→2，距离为 2
• 1→3：走 1→2→3，距离为 2+1=3（比直接走 1→3 的 5 更短）
• 1→4：走 1→2→3→4，距离为 2+1+1=4

数据范围

• 对于 20% 的数据，1 ≤ n ≤ 10，1 ≤ m ≤ 50
• 对于 40% 的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 1000
• 对于 60% 的数据，1 ≤ n ≤ 1000，1 ≤ m ≤ 10000
• 对于 80% 的数据，1 ≤ n ≤ 10000，1 ≤ m ≤ 100000
• 对于 100% 的数据，1 ≤ n ≤ 10^5，1 ≤ m ≤ 2×10^5，1 ≤ w ≤ 10^9

提示

本题建议使用 Dijkstra 算法（堆优化）求解，时间复杂度 O((n+m)log n)。