Given a directed graph, that can contain multiple edges and loops. Each edge has a weight that is expressed by a number (possibly negative). It is guaranteed that there are no cycles of negative weight.

Calculate the length of the shortest paths from the vertex number 1 to all other vertices.

Input

First the number of vertices n (1 ≤ n ≤ 100) is given. It is followed by the number of edges m (0 ≤ m ≤ 10000). Next m triples describe the edges: beginning of the edge, the end of the edge and its weight (an integer from -100 to 100).

Output

Print n numbers - the distance from the vertex number 1 to all other vertices of the graph. If the path to the corresponding vertex does not exist, instead of the path length print the number 30000.