Problems

# Ford-Bellman

# Ford-Bellman

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**.

Input example #1

4 5 1 2 10 2 3 10 1 3 100 3 1 -10 2 3 1

Output example #1

0 10 11 30000