← 返回题目列表

Codeforces · 2214/E

E. 最短路径

中文机器翻译题面 查看原题

给你一个由 $$$n$$$ 个节点和 $$$m$$$ 无向边组成的图。使用 Dikjstra 算法找到从节点 $$$1$$$ 到每个节点的最短路径。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(2 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2})$$$。

以下 $$$m$$$ 行每行包含 $$$3$$$ 整数:$$$u$$$、$$$v$$$ 和 $$$w$$$,表示从 $$$u$$$ 到 $$$v$$$ 的无向边,权重 $$$w$$$ $$$(1 \leq u, v \leq n, 0 \leq w \leq 10^5)$$$。

输出

输出从节点 $$$1$$$ 到每个节点 $$$2, \dots, n$$$ 的最短路径。如果从节点 $$$1$$$ 无法到达某个节点,则输出 $$$-1$$$。

示例

输入
复制

2 1
1 2 1

输出
复制

1

输入
复制

5 5
1 2 7
1 3 4
1 4 9
2 3 6
3 4 2

输出
复制

7
4
6
-1

输入
复制

5 6
1 5 2
2 1 6
3 4 2
4 2 9
5 3 7
2 3 4

输出
复制

6
9
12
2