题目描述

小核桃在一个 $n$ 个节点 $m$ 条边的有向图上做游戏。

小核桃有一个红色球和一个蓝色球。 游戏开始时，小核桃将红色球放在 $1$ 号节点上，将蓝色球放在 $i$ 号节点上。对于一条 $u \rightarrow v$ 长度为 $w$ 的有向边，小核桃可以花费 $w$ 的时间将球从 $u$ 点移动到 $v$ 点。 每局游戏中，小核桃要通过尽可能少的时间将两个球移动到任意同一个节点上。

小核桃同一时间只能操作一个球，现在小核桃想知道将蓝球放置于 $2\sim n$ 的每个点 ，每局游戏完成的最短时间是多少，如果游戏无法完成，输出 $-1$。

输入格式

第一行两个整数 $n,m$

接下来 $m$ 行，每行三个整数 $u,v,w$ ，表示一条边。

输出格式

一行 $n-1$ 个整数，表示蓝色球在 $2,3,...,n$ 号点的答案。

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

数据范围

$$\begin{aligned} & \bullet \ 2 \le n \le 10^5\\ & \bullet \ 0 \le m \le 2 \times 10^5\\ & \bullet \ 1 \le u_i,v_i \le n\\ & \bullet \ 1 \le w_i \le 10^9 \\ & 不含重边和自环 \end{aligned}$$