CF1725M.Moving Both Hands

Pak Chanek is playing one of his favourite board games. In the game, there is a directed graph with $N$ vertices and $M$ edges. In the graph, edge $i$ connects two different vertices $U_i$ and $V_i$ with a length of $W_i$. By using the $i$-th edge, something can move from $U_i$ to $V_i$, but not from $V_i$ to $U_i$.

To play this game, initially Pak Chanek must place both of his hands onto two different vertices. In one move, he can move one of his hands to another vertex using an edge. To move a hand from vertex $U_i$ to vertex $V_i$, Pak Chanek needs a time of $W_i$ seconds. Note that Pak Chanek can only move one hand at a time. This game ends when both of Pak Chanek's hands are on the same vertex.

Pak Chanek has several questions. For each $p$ satisfying $2 \leq p \leq N$, you need to find the minimum time in seconds needed for Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $1$ and vertex $p$, or report if it is impossible.

帕克·查内克正在玩他最喜爱的棋盘游戏之一。在该游戏中，存在一个包含 $N$ 个顶点和 $M$ 条边的有向图。图中第 $i$ 条边连接两个不同的顶点 $U_i$ 和 $V_i$，其长度为 $W_i$。利用第 $i$ 条边，某物可以从 $U_i$ 移动到 $V_i$，但不能从 $V_i$ 移动到 $U_i$。

为了进行该游戏，帕克·查内克初始时必须将他的两只手分别放在两个不同的顶点上。在一次操作中，他可以使用一条边将其一只手移动到另一个顶点。将一只手从顶点 $U_i$ 移动到顶点 $V_i$ 需要 $W_i$ 秒。注意：帕克·查内克每次只能移动一只手。当他的两只手最终位于同一顶点时，游戏结束。

帕克·查内克提出了若干问题。对每个满足 $2 \leq p \leq N$ 的 $p$，你需要求出：若初始时帕克·查内克的左手和右手分别位于顶点 $1$ 和顶点 $p$，则他结束游戏所需的最短时间（单位：秒）；若不可能实现，则报告不可能。

The first line contains two integers $N$ and $M$ ($2 \leq N \leq 10^5$, $0 \leq M \leq 2 \cdot 10^5$) — the number of vertices and edges in the graph.

The $i$-th of the next $M$ lines contains three integers $U_i$, $V_i$, and $W_i$ ($1 \le U_i, V_i \le N$, $U_i \neq V_i$, $1 \le W_i \le 10^9$) — a directed edge that connects two different vertices $U_i$ and $V_i$ with a length of $W_i$. There is no pair of different edges $i$ and $j$ such that $U_i = U_j$ and $V_i = V_j$.

第一行包含两个整数 $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$。

Output a line containing $N-1$ integers. The $j$-th integer represents the minimum time in seconds needed by Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex $1$ and vertex $j+1$, or $-1$ if it is impossible.

输出一行，包含 $N-1$ 个整数。其中第 $j$ 个整数表示：若游戏初始时 Pak Chanek 的左手和右手分别位于顶点 $1$ 和顶点 $j+1$，则 Pak Chanek 结束游戏所需的最短时间（单位：秒）；若无法结束游戏，则该整数为 $-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.

如果最初 Pak Chanek 的左手位于顶点 $1$，右手位于顶点 $5$，则 Pak Chanek 可以执行以下操作：

1. 将右手移动到顶点 $4$，耗时 $1$ 秒。
2. 将左手移动到顶点 $2$，耗时 $2$ 秒。
3. 将左手移动到顶点 $4$，耗时 $1$ 秒。

总共需要 $1+2+1=4$ 秒。可以证明不存在更快的方案。