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

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

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