← 返回题目列表

Codeforces · 1473/E

E. 最小路径

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

给您一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的加权无向连通图。保证给定图中不存在自环或重边。

让我们将由 $$$k$$$ 边组成的路径权重定义为 $$$\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}$$$,其中 $$$w_i$$$ — 图中第 $$$i$$$ 条边的权重。

您的任务是找到每个 $$$i$$$ ($$$2 \le i \le n$$$) 从 $$$1$$$-st 顶点到 $$$i$$$-th 顶点的路径的最小权重。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — 图中的顶点数和边数。

以下 $$$m$$$ 行包含三个整数 $$$v_i, u_i, w_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$1 \le w_i \le 10^9$$$; $$$v_i \neq u_i$$$) — 第 $$$i$$$ 条边的端点及其权重分别。

输出

打印 $$$n-1$$$ 整数 — 每个 $$$i$$$ 从 $$$1$$$-st 顶点到第 $$$i$$$ 个顶点的路径的最小权重 ($$$2 \le i \le n$$$)。

示例

输入 #1

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

输出 #1

1 2 2 4

输入 #2

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

输出 #2

2 1 4 3 1

输入 #3

7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4

输出 #3

3 4 2 7 7 3