E. Magikarp: Far From Home
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp likes to explore Karpville, but sometimes his phone runs out of battery when he is far from home. Karpville is made up of $$$n$$$ intersections and $$$m$$$ one-way streets, the $$$j$$$-th of which goes from intersection $$$u_j$$$ to intersection $$$v_j$$$ and takes $$$w_j$$$ minutes to drive.

Magikarp wonders, if he were to start at intersection $$$i$$$, what is the shortest amount of time (in minutes) it takes to reach his apartment, located at intersection $$$n$$$, if he is only allowed to drive? Help Magikarp answer this question for all intersections.

If Magikarp cannot drive back from some intersection, print $$$-1$$$ for that answer. Note that there can be multiple roads between the same pair of intersections.

Psst... the answers can exceed the size of a 32-bit integer!

Input

The first line of input contains $$$n$$$ and $$$m$$$ $$$(1\le n,m\le 2\cdot 10^5)$$$ — the number of intersections and the number of one-way streets, respectively.

The $$$j$$$-th of the next $$$m$$$ lines contains 3 integers $$$u_j$$$, $$$v_j$$$, and $$$w_j$$$ $$$(1\le u_j,v_j\le n, u_j\neq v_j, 0\le w_j\le 10^9)$$$ — the starting intersection, ending intersection, and distance (in minutes) for the $$$j$$$-th one-way road.

Output

Output $$$n$$$ lines, each containing a single integer. The $$$i$$$-th number should represent the shortest time (in minutes) it will take Magikarp to drive back to his apartment if he starts at intersection $$$i$$$, or $$$-1$$$ if this is impossible.

Examples
Input
3 3
1 2 1
2 3 2
1 3 5
Output
3
2
0
Input
6 9
1 2 1
2 1 0
5 2 0
3 2 4
4 5 3
3 4 2
3 5 7
5 6 2
5 6 0
Output
-1
-1
5
3
0
0