Dijkstra, tal qual P30288

Feu un programa que calculi el cost mínim d’anar d’un vèrtex a tots els altres en un graf dirigit amb pesos positius als arcs.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arcs m, seguits de m triplets x y c, que indiquen que hi ha un arc de x a y que té cost ‍c. Suposeu 2 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5n, que els vèrtexs es numeren entre 0 i n − 1, x ≠ y, que per a tot parell x y no hi ha més d’un arc d’anada i un de tornada, i que tots els costs c són naturals entre 1 i 10⁴.

Sortida

Per a cada cas, escriviu el cost mínim d’anar de 0 a cadascun dels altres vèrtexs, en ordre de 1 a n − 1. Si no hi ha camí fins a algun vèrtex, indiqueu-ho escrivint “no”. Escriviu una línia amb 10 guions al final de cada cas.