Carreteres curtes X50299

Considereu el mapa d’un país, amb $n$ ciutats (numerades entre 0 i $n-1$) i $m$ carreteres unidireccionals que les connecten. Cada carretera té una certa longitud. Volem anar de la ciutat 0 a la ciutat 1. Com que viatgem amb persones que es maregen, i no volem parar a estirar les cames a mitja carretera, volem seguir el camí tal que la carretera més llarga que faci servir sigui el més curta possible. És a dir, si el camí usa $k$ carreteres, amb longituds $\ell_1, \dots, \ell_k$, i $\ell = \max(\ell_1, \dots, \ell_k)$, volem que $\ell$ sigui tan petita com sigui possible.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $m$, seguits d’$m$ triplets $x$ $y$ $\ell$, amb $x \ne y$, indicant una carretera que va de $x$ a $y$ de longitud $\ell$. Suposeu $2 \le n \le 10^4$, $1 \le m \le 10n$, que no hi ha més d’una carretera d’$x$ a $y$ en aquest mateix ordre, que les longituds es troben entre 1 i $10^5$, i que sempre hi ha algun camí entre 0 i 1.

Sortida

Per a cada cas, escriviu la longitud màxima de les carreteres del millor camí possible.

La segona línia de l’exemple de sortida es correspon al camí $0 \to 4 \to 2 \to 1$, el qual té una carretera (la $0 \to 4$) de longitud màxima 80.

Pista

Considereu una variant de l’algorisme de Dijkstra.