Camí màxim P14985

Donat un graf dirigit sense cicles, on els arcs tenen costs (potser negatius), calculeu-ne el camí de cost màxim.

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arcs m, seguits d’m triplets x y c descrivint un arc des d’x fins a y de cost c, amb x ≠ y i | c | ≤ 10⁴. Suposeu 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 5n, que els vèrtexs es numeren a partir de 0, i que no hi ha més d’un arc d’x a y.

Sortida

Per a cada graf, escriviu el vèrtex inicial, el vèrtex final i el cost del camí de cost màxim. En cas d’empat, trieu el camí amb vèrtex inicial màxim. En cas d’un altre empat, trieu el camí amb vèrtex final màxim. Tingueu en compte que els camins buits tenen cost 0.