Given an undirected weighted graph, you need to find the distance from vertex 1 to all others using Dijkstra's algorithm.
Input:
Line 1 contains 2 integers n and m (n>=1, m>= 0), the number of vertices and edges in the graph, respectively. The next m lines contain 3 numbers each a and b - the vertices that the edge connects and c - the weight of this edge .
Output:
It is necessary to print n-1 numbers separated by a space - the distances from vertex 1 to all the rest, if there is no possible path from 1 to vertex i, then you need to print Impossible.
|
Enter |
Output |
|
5 5
|
2 3 1 Impossible |
P.S. Check Limits Carefully