Camí de cost mínim P64800

Escriviu un programa que, donat un graf dirigit amb costs positius als arcs, i dos vèrtexs $x$ i $y$, calculi un camí de cost mínim per anar des d’$x$ fins a $y$. Si n’hi ha més d’un, cal triar el més petit en ordre lexicogràfic.

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$ que indiquen que hi ha un arc $u \to v$ de cost $c$, amb $u \ne v$ i $1 \le c \le 1000$. Finalment, tenim $x$ i $y$. Assumiu $1 \le n \le 10^4$, $0 \le m \le 5n$, i que per a tot parell de vèrtexs $u$ i $v$ hi ha com a molt un arc $u \to v$. Tots els nombres són enters. Els vèrtexs es numeren entre 0 i $n-1$.

Sortida

Per a cada cas, escriviu el cost del camí més barat per anar des d’$x$ fins a $y$, seguit d’aquest camí. Si n’hi ha més d’un, escolliu el lexicogràficament més petit. Si no hi ha cap camí des d’$x$ fins a $y$, indiqueu-ho.

Pista

Comenceu en $y$.