Problem Description

You are given a directed weighted graph with $ N $ vertices and $ M $ edges.

The vertices are numbered from $ 1 $ to $ N $. Additionally, the $i\ (1\ \leq\ i\ \leq\ M)$ -th edge goes from vertex $ u_i $ to vertex $ v_i $ with a weight of $ w_i $.

For each $k=1,2,\ldots,N$, solve the following problem:

• Determine if there exists a path starting from vertex $ 1 $, passing through vertex $ k $ at least once, and ending at vertex $ N $. If such a path exists, output the length of the shortest one.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $\hspace{0.8cm}\vdots$ $ u_M $ $ v_M $ $ w_M $

Output Format

Output $ N $ lines. The $i\ (1\ \leq\ i\ \leq\ N)$ -th line should contain the answer for the case $ k=i $ as follows:

• If there exists a path starting from vertex $ 1 $, passing through vertex $ k $ at least once, and ending at vertex $ N $, output the length of the shortest such path.
• If no such path exists, output -1.

Sample Input and Output

Sample Input #1

3 3
1 2 3
2 3 4
1 3 2

Sample Output #1

2
7
2

Sample Input #2

5 10
2 1 1
2 5 5
1 2 6
2 5 4
5 3 2
1 3 1
1 3 4
3 5 4
1 5 3
5 2 3

Sample Output #2

3
10
5
-1
3

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ M\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ u_i,v_i\ \leq\ N$
• $u_i\ \neq\ v_i$
• $1\ \leq\ w_i\ \leq\ 10^9$
• All inputs are integers

Sample Explanation 1

• For $ k=1 $, the shortest path is directly moving to vertex $ 3 $ via the 3rd edge.
• For $ k=2 $, the shortest path is moving to vertex $ 2 $ via the 1st edge and then to vertex $ 3 $ via the 2nd edge.
• For $ k=3 $, the shortest path is directly moving to vertex $ 3 $ via the 3rd edge.

见题面 Input 部分

见题面 Output 部分