Moving Both Hands

Description:

Input:

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$$$.

Output:

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.

Sample Input:

5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1

Sample Output:

1 -1 3 4

Note:

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.