Supăraţi că lansarea părţii a treia a filmului lor preferat s-a amânat până în iunie $2018$, Henry şi Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:
Într-o lume în care vikingii pot zbura cu dragonii există $N$ insule. Hiccup, şeful tribului de vikingi aflat pe insula $1$, ştie $M$ rute directe de zbor *bidirecţionale* între insule. Pentru fiecare $j$ intre $1$ si $M$, ruta $j$ uneşte insulele $A{~j~}$ şi $B{~j~}$ şi are lungime $D{~j~}$.

Pe fiecare insulă $i$, $(1 ≤ i ≤ n)$ există dragoni din specia $i$ care pot zbura fără a se opri pentru odihnă o distanţă maximă $Dmaxi$. Cu alte cuvinte, dragonii de pe insula $i$ vor putea parcurge orice rută $j$, $(1 ≤ j ≤ m)$ pentru care $D{~j~}$ ≤ $Dmaxi$, indiferent de ce alte drumuri au făcut anterior.

Pe fiecare insulă $i$, $(1 ≤ i ≤ n)$ există dragoni din specia $i$ care pot zbura fără a se opri pentru odihnă o distanţă maximă $Dmax{~i~}$. Cu alte cuvinte, dragonii de pe insula $i$ vor putea parcurge orice rută $j$, $(1 ≤ j ≤ m)$ pentru care $D{~j~}$ ≤ $Dmax{~i~}$, indiferent de ce alte drumuri au făcut anterior.

Hiccup doreşte să ajungă de pe insula $1$ pe insula $N$ pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua iniţial un dragon din specia $1$ (de pe insula $1$). Apoi, dacă la un moment dat Hiccup se află pe o insula $i$, $(1 ≤ i ≤ n)$ având cu el un dragon din specia $t$, el poate:

In fişierul de ieşire _dragoni.out_ se va afişa un singur numar natural.
*Dacă valoarea lui $p$ este $1$, se rezolvă numai cerinţa a.*

În acest caz numărul afişat va reprezenta distanţa maximă $Dmaxi$ a unui dragon $i$ la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat iniţial de pe insula $1$.

În acest caz numărul afişat va reprezenta distanţa maximă $Dmax{~i~}$ a unui dragon $i$ la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat iniţial de pe insula $1$.

*Daca valoarea lui $p$ este $2$, se va rezolva numai cerinţa b.*
În acest caz numărul afişat va reprezenta distanţa minima pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula $1$ pe insula $N$.