== 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.