E. Shortest Paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a graph of $$$n$$$ nodes and $$$m$$$ undirected edges. Find the shortest path from node $$$1$$$ to each node with Dikjstra's algorithm.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(2 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2})$$$.

The following $$$m$$$ lines contain $$$3$$$ integers each: $$$u$$$, $$$v$$$, and $$$w$$$, denoting an undirected edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$ $$$(1 \leq u, v \leq n, 0 \leq w \leq 10^5)$$$.

Output

Output the shortest path from node $$$1$$$ to each node $$$2, \dots, n$$$. If a node is not reachable from node $$$1$$$, output $$$-1$$$.

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