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 \le n \le 10^4$, $0 \le m \le 5n$, que els vèrtexs es numeren entre 0 i $n - 1$, $x \ne 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^4$.

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.