Pak Chanek 正在玩他最喜欢的棋盘游戏之一。游戏中有一个有向图,其顶点为$$$N$$$,边为$$$M$$$。在图中,边 $$$i$$$ 连接两个不同的顶点 $$$U_i$$$ 和 $$$V_i$$$,长度为 $$$W_i$$$。通过使用第 $$$i$$$ 条边,某些东西可以从 $$$U_i$$$ 移动到 $$$V_i$$$,但不能从 $$$V_i$$$ 移动到 $$$U_i$$$。
要玩这个游戏,最初 Pak Chanek 必须将双手放在两个不同的顶点上。在一次移动中,他可以使用边缘将一只手移动到另一个顶点。为了将手从顶点 $$$U_i$$$ 移动到顶点 $$$V_i$$$,Pak Chanek 需要 $$$W_i$$$ 秒的时间。请注意,Pak Chanek 一次只能移动一只手。当 Pak Chanek 的双手位于同一顶点时,游戏结束。
Pak Chanek 有几个问题。对于每个满足 $$$2 \leq p \leq N$$$ 的 $$$p$$$,如果最初 Pak Chanek 的左手和右手分别放在顶点 $$$1$$$ 和顶点 $$$p$$$ 上,则需要找到 Pak Chanek 结束游戏所需的最短时间(以秒为单位),如果不可能则报告。
输入
第一行包含两个整数 $$$N$$$ 和 $$$M$$$ ($$$2 \leq N \leq 10^5$$$, $$$0 \leq M \leq 2 \cdot 10^5$$$) — 图中顶点和边的数量。
接下来的 $$$M$$$ 行的第 $$$i$$$ 行包含三个整数 $$$U_i$$$、$$$V_i$$$ 和 $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$U_i \neq V_i$$$, $$$1 \le W_i \le 10^9$$$) — 连接两个不同顶点 $$$U_i$$$ 和 $$$V_i$$$ 的有向边,长度为 $$$W_i$$$。不存在一对不同的边 $$$i$$$ 和 $$$j$$$ 使得 $$$U_i = U_j$$$ 和 $$$V_i = V_j$$$。
输出
输出包含 $$$N-1$$$ 整数的行。第 $$$j$$$ 整数表示如果 Pak Chanek 的左手和右手最初放置在顶点 $$$1$$$ 和顶点 $$$j+1$$$ 上,则 Pak Chanek 结束游戏所需的最短时间(以秒为单位),如果不可能,则为 $$$-1$$$。
示例
输入 #1
5 7 1 2 2 2 4 1 4 1 4 2 5 3 5 4 1 5 2 4 2 1 1
输出 #1
1 -1 3 4
注意
如果最初 Pak Chanek 的左手位于顶点 $$$1$$$ 且右手位于顶点 $$$5$$$,则 Pak Chanek 可以执行以下动作:
1. 在$$$1$$$秒内将右手移至顶点$$$4$$$。
2. 在 $$$2$$$ 秒内将左手移至顶点 $$$2$$$。
3. 在 $$$1$$$ 秒内将左手移至顶点 $$$4$$$。
总共需要 $$$1+2+1=4$$$ 秒。可以证明没有其他方法更快。