题目背景

Moving Both Hands - 洛谷

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

Alice 在进行一个有向图上做游戏。有向图上共有 $n$ 个节点，$m$ 条有向边。Alice的手上有 一个红色球和一个蓝色球。 游戏开始时，Alice将红色球放在 $1$ 号节点上，将蓝色球放在 $i$ 号节点上。 长度为 $w$ 的有向边表示可以通过一次操作将在 $v$ 的点转移 到 $u$ 花费 $w$时间。 每局游戏中，Alice 要通过尽可能少的时间将两个球共同转移到任意同一个节点上。Alice 同一时间只能操作一个球。现在 Alice 想知道对于每个点 $2\le i \le n$ ，每局游戏完成的最小时间是 多少。

输入格式

输入第一行是两个整数 $n$ ，$m$。 接下来 $m$行，每行三个整数 $u$，$v$，$w$，表示图上有一条从 $u$ 指向 $v$ 长为 $w$ 的有向边。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 行的整数表示蓝色球开始时在 $i$ 号点上时游戏的 最小完成时间。如果不能完成游戏，输出 -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 3 4

提示

如果最初白昌旭的左手在顶点 $1$，右手在顶点 $5$，白昌旭可以下出以下棋步：

1. 在 $1$ 秒内将右手移至顶点 $4$。
2. 在 $2$ 秒内将左手移至顶点 $2$。
3. 在 $1$ 秒内将左手移至顶点 $4$。

总共需要 $1+2+1=4$ 秒。可以证明，没有其他更快的方法了。