Editing 1136 - Dragoni (section)

== Enunț ==
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ă <code>N</code> insule. Hiccup, șeful tribului de vikingi aflat pe insula <code>1</code>, știe <code>M</code> rute directe de zbor bidirecționale între insule. Pentru fiecare <code>j</code> intre <code>1</code> si <code>M</code>, ruta <code>j</code> unește insulele <code>Aj</code> și <code>Bj</code> și are lungime <code>Dj</code>.

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

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

# Să zboare de pe insula <code>i</code> pe o altă insulă <code>x</code> cu dragonul pe care îl are, folosind o rută directă <code>j</code> între insulele <code>i</code> si <code>x</code>, bineînțeles doar dacă <code>Dj ≤ Dmaxt</code>.
# Să schimbe dragonul din specia <code>t</code> pe care îl are cu un dragon din specia <code>i</code> aflat pe insula respectivă.