Campaña electoral P24183

Considerad un país con n ciudades y m carreteras bidireccionales, cada una de las cuales tiene una cierta longitud. Un político que vive en la ciudad p está de campaña electoral, y deberá visitar el país en coche. Pero cada vez que llegue a una ciudad, aunque sea de paso, el político tendrá que bajar del coche, sonreír, dar la mano, besar a niños pequeños, prometer subir las pensiones de los abuelos, …, que pereza! Así que el político quiere saber, para cada ciudad c, como ir desde p hasta c haciendo el mínimo número de paradas. En caso de empate, quiere minimizar la longitud total del trayecto. ¿Le podéis ayudar?

Entrada

La entrada consiste en varios casos. Cada caso empieza con n y m, seguidas de m triplas x ‍y ‍ℓ para una carretera entre x e y de longitud ℓ, con x ≠ y. Cada caso acaba con p. Suponed 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 5n, que las ciudades se numeran a partir de 0, que no hay más de una carretera entre dos ciudades, y que las longitudes son números naturales entre 1 y 10⁴.

Salida

Para cada caso, y para cada ciudad c, escribid el número de paradas y la longitud total para ir desde p hasta c. Si no se puede llegar a c, indicadlo. Escribid una línea con 10 guiones al final de cada caso.

Observación

El Jutge puede aceptar soluciones con una variante del algoritmo de Dijkstra, pero la solución esperada tiene una complejidad mejor. Quien use Dijkstra obtendrá una nota máxima de 7.