Description

小妖精侵占了农场。这些讨厌的类精灵生物会阻挠每头牛从谷仓（位于 $\mathrm{pasture}_1$（牧场 $1$））前往其他牧场的行程，其中第 $i$ 头牛要从 $\mathrm{pasture}_1$ 前往 $\mathrm{pasture}_i$。每个小妖精都经过个性化训练，知道第 $i$ 头牛前往 $\mathrm{pasture}_i$ 的最短路径。第 $i$ 个小妖精会埋伏在第 $i$ 头牛最短路径的最后一条道路上，企图骚扰这头牛。

每头牛当然都不希望被骚扰，因此会选择一条与原始最短路径至少存在细微差别的从 $\mathrm{pasture}_1$ 到 $\mathrm{pasture}_i$ 的新路径。

请计算每头牛避开位于其原始最短路径最后一条道路上的小妖精后，新路线的最短通行时间。

给定 $M (2 \leq M \leq 200\,000)$ 条双向道路（编号 $1\dots M$）连接 $N (3 \leq N \leq 100\,000)$ 个牧场（编号 $1\dots N$）。第 $i$ 条道路连接牧场 $a_i (1 \leq a_i \leq N)$ 和 $b_i (1 \leq b_i \leq N)$，通行时间为 $t_i (1 \leq t_i \leq 1\,000)$。保证没有两条道路连接同一对牧场，且所有测试数据中从 $\mathrm{pasture}_1$ 到任意 $\mathrm{pasture}_i$ 的最短路径唯一。

例如以下牧场、道路和通行时间：

1--[2]--2-------+ 
|       |       | 
[2]     [1]     [3] 
|       |       | 
+-------3--[4]--4

TRAVEL     最佳路线      最短时间    最后一条道路 
p_1 到 p_2   1->2          2         1->2 
p_1 到 p_3   1->3          2         1->3 
p_1 到 p_4  1->2->4        5         2->4 

当存在小妖精时：

TRAVEL     最佳路线      最短时间    规避道路 
p_1 到 p_2   1->3->2        3         1->2 
p_1 到 p_3   1->2->3        3         1->3 
p_1 到 p_4   1->3->4        6         2->4 

• 对于 $20\%$ 的测试数据，$N\leq 200$。
• 对于 $50\%$ 的测试数据，$N\leq 3000$。

Input Format

• 第 $1$ 行：两个空格分隔的整数 $N$ 和 $M$
• 第 $2\dots (M+1)$ 行：每行三个空格分隔的整数 $a_i$、$b_i$ 和 $t_i$

Output Format

• 第 1..N-1 行：第 $i$ 行输出从 $\mathrm{pasture}_1$ 到 $\mathrm{pasture}_{i+1}$ 时，避开其原始最短路径最后一条道路后的新最短路径时间。若不存在这样的路径，输出 -1。

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

3 
3 
6