Campanya electoral P24183

Considereu un país amb n ciutats i m carreteres bidireccionals, cadascuna amb una certa longitud. Un polític que viu a la ciutat p està de campanya electoral, i haurà de visitar el país en cotxe. Però cada vegada que arribi a una ciutat, encara que sigui de passada, el polític haurà de baixar del cotxe, somriure, encaixar mans, fer petons a nens petits, prometre apujar les pensions dels avis, …, quina mandra! Així que el polític vol saber, per a cada ciutat c, com anar des de p fins a c fent el mínim nombre de parades. En cas d’empat, vol minimitzar la longitud total del trajecte. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguides d’m triplets x y ℓ descrivint una carretera entre x i y de longitud ℓ, amb x ≠ y. Cada cas acaba amb p. Suposeu 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 5n, que les ciutats es numeren a partir de 0, que no hi ha més d’una carretera entre dues ciutats, i que les longituds són nombres naturals entre 1 i 10⁴.

Sortida

Per a cada cas, i per a cada ciutat c, escriviu el nombre de parades i la longitud total per anar des de p fins a c. Si no es pot arribar a c, indiqueu-ho. Escriviu una línia amb 10 guions al final de cada cas.

Observació

El Jutge pot acceptar solucions amb una variant de l’algorisme de Dijkstra, però la solució esperada té una complexitat millor. Qui usi Dijkstra obtindrà una nota màxima de 7.