← 返回题目列表

Codeforces · 1725/M

M. 移动双手

中文机器翻译题面 查看原题

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$$$ 秒。可以证明没有其他方法更快。