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