CF1473E Minimum Path

题目描述

给定一个包含 $n$ 个顶点和 $m$ 条边的无向连通带权图。保证图中没有自环和重边。

我们定义一条由 $k$ 条编号为 $e_1, e_2, \dots, e_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$ 个顶点到第 $i$ 个顶点的路径的最小权值。

输入格式

第一行包含两个整数 $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$ 个顶点到第 $i$ 个顶点的最小路径权值（$2 \le i \le n$）。

输入输出样例 #1

输入 #1

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

输出 #1

1 2 2 4

输入输出样例 #2

输入 #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

输入 #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

说明/提示

由 ChatGPT 4.1 翻译