You are given 2 integers $(N , M)$, N is the number of vertices, M is the number of edges. You'll also be given $a_i$ , $b_i$, $w_i$ where $a_i$ and $b_i$ represents an edge from a vertex $a_i$ to a vertex $b_i$ and $w_i$ respresents the weight of that edge.

Task is to find the shortest path from source vertex (vertex number 1) to all other vertices ($v_i$) where ($2 \le i \le N$).

Input:

First line contains two space separated integers, $(N , M)$ Then M lines follow, each line has 3 space separated integers $a_i$ , $b_i$, $w_i$.

Output:
Print the shortest distances from the source vertex (vertex number 1) to all other vertices ($v_i$) where ($2 \le i \le N$). Print "$10 ^ 9$" in case the vertex "$v_i$" can't be reached form the source vertex.
Leave a space between any 2 printed numbers.

Constraints:
$(1 \le N \le 10^4)$
$(1 \le M \le 10^6)$
$(1 \le a_i, b_i \le N)$
$(1 \le w_i \le 1000)$