== include(page="template/taskheader" task_id="dragoni") ==

Supăraţi că lansarea părţii a treia a filmului lor preferat s-a amânat până în martie $2019$, Henry şi Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:

Supăraţi că lansarea părţii a treia a filmului lor preferat s-a amânat până în februarie $2019$, 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ă $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.

Zboară de pe insula $2$ pe insula $3$ o distanţă de $6$ cu dragonul din specia $1$.
Schimbă dragonul din specia $1$ cu dragonul aflat pe insula $3$, care poate zbura o distanţă maximă de $13$.
Zboară de pe insula $3$ pe insula $1$ o distanţă de $7$ cu dragonul din specia $3$.

Zboară de pe insula $1$ pe insula $5$ o distanţă de $1$0 cu dragonul din specia $3$.

Zboară de pe insula $1$ pe insula $5$ o distanţă de $10$ cu dragonul din specia $3$.

În total el parcurge o distanţă de $5 + 6 + 7 + 10 = 28$.