Problem
Escriba un programa que encuentre las distancias en un gráfico ponderado no dirigido con longitudes de borde no negativas, desde un vértice dado hasta cualquier otro vértice. El programa debe ser rápido para gráficos grandes y dispersos.
Entrada
La primera línea de la entrada contiene el número NUM — el número de ejecuciones diferentes del algoritmo de Dijkstra (en diferentes gráficos). A esto le siguen NUM bloques, cada uno de los cuales tiene la siguiente estructura.
La primera línea del bloque contiene dos números N y M separados por un espacio — el número de vértices y el número de aristas del gráfico. A esto le siguen líneas M , cada una de las cuales contiene tres números enteros separados por espacios. Los dos primeros, que van de 0 a N–1 cada uno, indican los extremos de la arista correspondiente, el tercero — que va de 0 a 20000 y denota la longitud de este borde. Además, en la última línea del bloque, un solo número de 0 a N–1 — pico, la distancia desde la que necesita buscar.
La cantidad de gráficos diferentes en una prueba NUM no supera los cinco. El número de vértices no supera los 60000, las aristas — 200000.
Impresión
Imprime en salida estándar (pantalla) NUM líneas, cada una con Ni números separados por espacios — la distancia desde el vértice inicial especificado del gráfico no dirigido ponderado hasta su 0, 1, 2, etc. vértices (se permite un espacio adicional después del último número). Si algún vértice es inalcanzable desde el inicial especificado, imprima el número 2009000999 en lugar de la distancia (se garantiza que todas las distancias reales son menores).
Ejemplos
| # |
Entrada |
Salida |
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |