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:

Î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 \leq i \leq 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 \leq j \leq m$) pentru care $D_j \leq 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 \leq i \leq 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$ ≤ $Dmax_t$.
2. Să schimbe dragonul din specia $t$ pe care îl are cu un dragon din specia $i$ aflat pe insula respectivă.

Cerințe

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

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

Date de ieșire

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

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

Restricții și precizări

• $1 \leq N \leq 800$
• $1 \leq M \leq 6000$
• $1 \leq Dmax_i \leq 50000$, pentru orice $1 \leq i \leq N$.
• $1 \leq A_j, B_j \leq N$, pentru orice $1 \leq j \leq M$.
• $1 ≤ D_j \leq 50000$, pentru orice $1 \leq j \leq 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 $10^9$.
• 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.

Exemplul 1

dragoni.in

1
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14

dragoni.out

20

Explicație

$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$ și $4$, întrucât pentru a ajunge pe insula $5$ el ar fi obligat sa parcurgă o ruta de lungime mai mare decât $6$.
Distanța maximă 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.

Exemplul 2

dragoni.in

2
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14

dragoni.out

28

Explicație

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:
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$.
În total el parcurge o distanță de $5 + 6 + 7 + 10 = 28$.