== 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 iunie 2018, 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 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ă $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.

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:

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:

1. Să zboare de pe insula $i$ pe o altă insulă $x$ cu dragonul pe care îl are, folosind o rută directă $j$ între insulele $i$ si $x$, bineînţeles doar dacă $D{~j~}$ ≤ $Dmaxt$.

* $1 ≤ Dj ≤ 50 000$, pentru orice $1 ≤ j ≤ M$.
* Se garantează că Hiccup poate ajunge pe insula $N$.
* Se garantează că răspunsul oricărei cerinţe este un număr natural mai mic decât $109$.

* Pentru rezolvarea corectă a primei cerinţe se acordă 20% din punctajul testului respectiv.
* Pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 80% din punctajul testului respectiv.
 

* Pentru rezolvarea corectă a primei cerinţe se acordă $20%$ din punctajul testului respectiv.
* Pentru rezolvarea corectă a celei de-a doua cerinţe se acordă $80%$ din punctajul testului respectiv.

h2. Exemplu

h3. Explicaţie

În primul exemplu P = 1 deci se va rezolva cerinţa a).

În primul exemplu $P = 1$ deci se va rezolva cerinţa a).

Există N = 5 insule si M = 6 rute între ele. Hiccup porneşte de pe insula 1 având un dragon care poate zbura o distanţă de maxim 6. Cu acest dragon poate ajunge doar pe insulele 1, 2, 3 si 4, întrucât pentru a ajunge pe insula 5 el ar fi obligat sa parcurgă o ruta de lungime mai mare decât 6.

Există $N = 5$ insule si $M = 6$ rute între ele. Hiccup porneşte de pe insula $1$ având un dragon care poate zbura o distanţă de maxim $6$. Cu acest dragon poate ajunge doar pe insulele $1, 2, 3$ si $4$, întrucât pentru a ajunge pe insula $5$ el ar fi obligat sa parcurgă o ruta de lungime mai mare decât $6$.

Distanta maxima pe care o poate zbura un dragon aflat pe insulele 1, 2, 3 sau 4 este deci 20 (dragonul de pe insula 4). Se observă că dragonul care poate zbura o distanţă de 26 se afla pe insula 5 şi este inaccesibil.

Distanta maxima pe care o poate zbura un dragon aflat pe insulele $1, 2, 3$ sau $4$ este deci $20$ (dragonul de pe insula $4$). Se observă că dragonul care poate zbura o distanţă de $26$ se afla pe insula $5$ şi este inaccesibil.

În al doilea exemplu P = 2 deci se va rezolva cerinţa b).

În al doilea exemplu $P = 2$ deci se va rezolva cerinţa b).

Există N = 5 insule şi M = 6 rute între ele. Pentru a parcurge o distanţă minimă de 28 între insulele 1 şi N, Hiccup face următorii paşi:

Există $N = 5$ insule şi $M = 6$ rute între ele. Pentru a parcurge o distanţă minimă de 28 între insulele $1$ şi $N$, Hiccup face următorii paşi:

Zboară de pe insula 1 pe insula 2 o distanţă de 5 cu dragonul din specia 1.
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 10 cu dragonul din specia 3.

Zboară de pe insula $1$ pe insula $2$ o distanţă de $5$ cu dragonul din specia $1$.
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$.

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

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

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