+ Time Limit: 1 second + Memory Limit: 256 megabytes ---------- We have a weighted and directed graph $G$ with $n$ vertices and $m$ edges. The vertices of this graph are numbered from $1$ to $n$. We ask you to write a program to print the shortest distance from vertex 1 to all vertices. (If there is no path from vertex 1 to a vertex, represent the distance as `-1`.) # Input In the first line of input, two integers $n$ and $m$ separated by a space are given, indicating the number of vertices and edges of graph $G$ respectively. $$1 \leq n \leq 300,000$$ $$0 \leq m \leq 300,000$$ In the next $m$ lines, each line contains three integers $u$, $v$, and $w$, representing the existence of an edge from vertex $u$ to vertex $v$ with weight $w$. $$1 \leq u, v \leq n$$ $$1 \leq w \leq 10^9$$ # Output In one line, print the distance from vertex 1 to all vertices in order. The distance from vertex 1 to itself is 0. If there is no path from 1 to a vertex, represent the distance as `-1`. # Example ## Sample Input 1 ``` 5 7 1 2 10 2 1 7 1 5 2 3 4 4 1 3 5 3 5 4 5 3 1 ``` ## Sample Output 1 ``` 0 10 3 7 2 ``` ## Sample Input 2 ``` 2 5 1 1 5 2 2 3 1 2 2 2 1 3 1 2 4 ``` ## Sample Output 2 ``` 0 2 ```