You are given a directed weighted graph. You need to find the distance from the top 1 to all the others, using the algorithm 1 - k BFS.
Input
The first line contains 2 integers n and m, the number of vertices and edges in the graph, respectively. The following m lines contain 3 numbers each a and b - the vertices that the edge connects and c - the weight of this edge (a, b, c >= 0).
Output
It is necessary to output n-1 number separated by a space - the distances from the top 1 to all the others, if there is no possible path from 1 to i< /code> vertex, then you need to output Impossible.
Examples
| # |
Input |
Output |
| 1 |
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
|
1 4 3 6 4 Impossible Impossible Impossible
|