Ford-Bellman#1453
A directed graph is given, in which multiple edges and self-loops are allowed. Each edge has an integer weight (including negative values). It is guaranteed that the graph contains no negative-weight cycles.
You are required to find the lengths of the shortest paths from vertex number to all other vertices of the graph.
The first line contains two integers: the number of vertices n~(1 \le n \le 100) and the number of edges m~(0 \le m \le 10000).
Then follow triples of integers describing the edges: the start vertex, the end vertex, and the weight of the edge. The weight is an integer in the range from to .
Print integers — the shortest distances from vertex number to each vertex of the graph.
If there is no path to a vertex, print the number instead of the path length.
Example 1