CF1725M Moving Both Hands

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 - 1$ 个整数，由空格隔开，第 $i$ 个整数表示蓝色球开始时在 $i$ 号点上时游戏的最小完成时间。如果不能完成游戏，输出 -1 。

If initially Pak Chanek's left hand is on vertex $ 1 $ and his right hand is on vertex $ 5 $ , Pak Chanek can do the following moves: 1. Move his right hand to vertex $ 4 $ in $ 1 $ second. 2. Move his left hand to vertex $ 2 $ in $ 2 $ seconds. 3. Move his left hand to vertex $ 4 $ in $ 1 $ second.  In total it needs $ 1+2+1=4 $ seconds. It can be proven that there is no other way that is faster.