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 → v de cost c, amb u ≠ v i 1 ≤ c ≤ 1000. Finalment, tenim x i y. Assumiu 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5n, i que per a tot parell de vèrtexs u i v hi ha com a molt un arc u → 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.