You are given 2 integers (N, M). N is 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.

Your task is to find the shortest path from source vertex (vertex number 1) to all other vertices v(i) where (2 <= i <= N).

Input:

First line contains two space separated integers, (N, M) them M lines follw, each line has 3 space separated integes a(i), b(i) and w(i).

Output:

Print the shortest distances from the source vertex (vertex number 1) to all other vertices v(i) where (2 <= i <= N). Print "10⁹" in case vertex v(i) can't be reached from the source vertex.

Leave a space between any 2 printed numbers.

Constrains:

(1 <= N <= 10⁴).

(1 <= M <= 10⁶).

(1 <= a_i, b_i <= N).

(1 <= w_i <= 1000).