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$）。

由 ChatGPT 4.1 翻译