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

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ă $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$.

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ă $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$.

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