Problem
Se le proporciona un gráfico ponderado dirigido. Necesitas encontrar la distancia desde el 1 superior a todos los demás, usando el algoritmo 1 - k BFS.
Entrada
La primera línea contiene 2 números enteros n y m, el número de vértices y aristas en el gráfico, respectivamente. Las siguientes líneas m contienen 3 números cada uno a y b - los vértices que conecta el borde y c - el peso de esta arista (a, b, c >= 0).
Salida
Es necesario generar el número n-1 separado por un espacio: las distancias desde el 1 superior a todos los demás, si no hay una ruta posible desde 1 a i< /code> vértice, luego debe generar Impossible.
Ejemplos
| # |
Entrada |
Salida |
| 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 Imposible Imposible Imposible
|