CF1725M Moving Both Hands

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

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

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

对于所有的数据，满足 $ 2 \leq n \leq 10^5 $，$ 0 \leq m \leq 2 \times 10^5 $，$1 \le u_i, v_i \le n $, $ u_i \neq v_i $，$ 1 \le w_i \le 10^9 $。