Problem Description

Given a directed graph with $n$ vertices and $m$ edges, find the shortest path lengths from vertex $1$ to every other vertex.

Note that the graph may contain multiple edges and self-loops, but it is guaranteed that there are no negative cycles.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain three integers $u_i$, $v_i$, and $w_i$, representing a directed edge from $u_i$ to $v_i$ with length $w_i$.

Output Format

Output one line with $n$ integers, where the $i$-th integer represents the shortest path length from vertex $1$ to vertex $i$. If there is no path from vertex $1$ to vertex $i$, the $i$-th integer should be replaced with $-1$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0 1 3 -1

Input Sample #2

10 50
5 9 6
1 3 10
3 1 1
10 2 5
8 5 1
10 10 6
6 5 2
1 5 10
2 5 5
10 1 4
1 5 2
8 8 7
7 2 7
9 2 8
3 1 4
6 2 5
3 9 9
4 9 5
5 10 9
10 1 9
5 4 5
9 1 2
5 10 6
3 8 7
10 3 7
5 8 8
9 2 6
9 8 6
3 2 8
1 3 8
1 10 1
7 8 4
9 4 5
4 6 2
2 7 6
10 1 5
9 9 7
6 7 4
1 1 7
8 3 10
8 3 9
10 9 8
3 9 1
7 4 8
1 5 4
8 4 4
3 4 4
9 9 2
2 10 4
8 9 6

Output Sample #2

0 6 8 7 2 9 12 10 8 1

Notes

There are no partial points for this problem.

For all data, $1 \leq n, m \leq 2 \times 10^3$, $-10^9 \leq w_i \leq 10^9$.

Please note the upper bound of the answer, which may require the use of long long int in C++.

见题面 Input 部分

见题面 Output 部分