== 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 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ă $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:
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. 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~}$ ≤ $Dmax{~t~}$.
2. Să schimbe dragonul din specia $t$ pe care îl are cu un dragon din specia $i$ aflat pe insula respectivă.
h2. Cerinţe
a. Să se determine distanţa maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat iniţial de pe insula $1$.
a. Să se determine distanţa maxima $Dmax{~i~}$ caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat iniţial de pe insula $1$.
b. Să se determine distanţa minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula $1$ pe insula $N$.
h2. Date de intrare
Fişierul de intrare _dragoni.in_ conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$. Pe a doua linie se găsesc două numere naturale $N$ şi $M$ reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc $N$ numere naturale, al $i$-ulea dintre acestea reprezentând distanta maximă Dmaxi pe care o poate zbura un dragon de pe insula $i$. Pe următoarele $M$ linii sunt descrise cele $M$ rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale $A, B$ şi $D$ cu semnificaţia că există rută *bidirecţională* de lungime $D$ între insulele $A$ şi $B$.
Fişierul de intrare $dragoni.in$ conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$. Pe a doua linie se găsesc două numere naturale $N$ şi $M$ reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc $N$ numere naturale, al $i$-ulea dintre acestea reprezentând distanta maximă $Dmax{~i~}$ pe care o poate zbura un dragon de pe insula $i$. Pe următoarele $M$ linii sunt descrise cele $M$ rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale $A, B$ şi $D$ cu semnificaţia că există rută *bidirecţională* de lungime $D$ între insulele $A$ şi $B$.
h2. Date de ieşire
In fişierul de ieşire _dragoni.out_ se va afişa un singur numar natural.
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$.
* $1 ≤ N ≤ 800$
* $1 ≤ M ≤ 6000$
* $1 ≤ Dmaxi ≤ 50 000$, pentru orice $1 ≤ i ≤ N$.
* $1 ≤ Aj, Bj ≤ N$, pentru orice $1 ≤ j ≤ M$.
* $1 ≤ Dj ≤ 50 000$, pentru orice $1 ≤ j ≤ M$.
* $1 ≤ Dmax{~i~} ≤ 50 000$, pentru orice $1 ≤ i ≤ N$.
* $1 ≤ A{~j~}, B{~j~} ≤ N$, pentru orice $1 ≤ j ≤ M$.
* $1 ≤ D{~j~} ≤ 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$.
* Se garantează că răspunsul oricărei cerinţe este un număr natural mai mic decât $1 000 000 000$.
* 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.
