给你一个由 $$$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 11 2 1
输出复制
1
输入复制
5 51 2 71 3 41 4 92 3 63 4 2
输出复制
7 4 6 -1
输入复制
5 61 5 22 1 63 4 24 2 95 3 72 3 4
输出复制
6 9 12 2