Millor que Dijkstra P42012

Feu un programa que, donat un graf dirigit amb pesos que poden ser 1, 2 o 3, calculi el cost mínim d’anar del vèrtex 0 a la resta de vèrtexs.

Qui resolgui aquest problema amb l’algorisme de Dijkstra obtindrà com a molt un 7, perquè hi ha una manera asimptòticament millor.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs $n$ i el nombre d’arcs $m$. Segueixen $m$ triplets $u$ $v$ $c$ indicant un arc $u \to v$ de cost $c$, amb $u \ne v$ i $1 \le c \le 3$. Assumiu $1 \le n \le 10^4$, $0 \le m \le 5n$, i que entre tot parell de vèrtexs $u$ i $v$ hi ha com a molt un arc $u \to v$. Els vèrtexs es numeren entre 0 i $n-1$.

Sortida

Per a cada cas, i per a cada vèrtex $v$, escriviu el cost mínim d’anar de 0 fins a $v$. Si és impossible, escriviu “no”. Escriviu una línia amb 10 guions al final de cada cas.