CF1473E.Minimum Path

You are given a weighted undirected connected graph consisting of $n$ vertices and $m$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Let's define the weight of the path consisting of $k$ edges with indices $e_1, e_2, \dots, e_k$ as $\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}$, where $w_i$ — weight of the $i$-th edge in the graph.

Your task is to find the minimum weight of the path from the $1$-st vertex to the $i$-th vertex for each $i$ ($2 \le i \le n$).

给你一个包含 $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$ 个顶点的路径的最小权重。

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^5$) — the number of vertices and the number of edges in the graph.

Following $m$ lines contains three integers $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$) — endpoints of the $i$-th edge and its weight respectively.

第一行包含两个整数 $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$ 条边的两个端点及其权重。

Print $n-1$ integers — the minimum weight of the path from $1$-st vertex to the $i$-th vertex for each $i$ ($2 \le i \le n$).

输出 $n-1$ 个整数——对每个 $i$（$2 \le i \le n$），输出从第 $1$ 个顶点到第 $i$ 个顶点的路径的最小权重。