给您一个由 $$$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