Module: bfs. advanced course


Problem

2 /3


1-k BFS

Problem

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 
 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!