You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai, bi and wi where ai and bi represents an edge from a vertex ai to a vertex bi and wi respresents the weight of that edge. Your task is to find the shortest path from source vertex (vertex number 1) to all other vertices. Note : use bellman ford algo.
Input Format
First line contains two space separated integers,N and M. Then M lines follow, each line has 3 space separated integers ai, bi and wi.
Output Format
Print the shortest distances from the source vertex (vertex number 1) to all other vertices in a line. Print 10^9 in case the vertex can't be reached form the source vertex.
Constraints
1<= N <= 10^4 1<= M <= 10^6 1<= ai, bi <= N -1000 <= wi <= 1000
Example
Input
5 5 1 2 5 1 3 2 3 4 1 1 4 6 3 5 5
Output
5 2 3 7