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 Aj și Bj și are lungime Dj.

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 Dj ≤ Dmaxi, 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ă Dj ≤ Dmaxt.
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 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.

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 Aj și Bj și are lungime Dj.

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 Dj ≤ Dmaxi, 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ă Dj ≤ Dmaxt.
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 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.
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 numărul 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-lea 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.

Date de ieșire

n fișierul de ieșire dragoni.out se va afișa un singur număr 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.

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

Distanta maxima 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 1

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 a).

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.

#include <bits/stdc++.h>


using namespace std;
#define Inf 0x3f3f3f3f

ifstream cin("dragoni.in");
ofstream cout("dragoni.out");

using PI = pair<int , int>;
int cer , n , m , x , y , w , dr[1001] , v[1001] , s , D[1001][1001] , d[10001];
vector <pair<int , int>> G[801];

void dfs(int nod , int dist , int &s)
{
    v[nod] = 1;
    for(auto x : G[nod])
        if(!v[x.first] && x.second <= dist)
        {
           v[x.first] = 1;
           if(dr[x.first] > s)
                s = dr[x.first];
           dfs(x.first , dist , s);
        }
}

void dijkstra(int s)
{
    priority_queue <PI , vector<PI> , greater<PI>> Q;
    D[s][s] = 0;
    Q.push({0 , s});
    while(!Q.empty())
    {
       x = Q.top().second;
       y = Q.top().first;
       Q.pop();
       if(y > D[s][x]) continue;
       for(auto& i:G[x])
       {
           int nodnou = i.first;
           int costnou = i.second;
           if(dr[s] >= costnou && D[s][nodnou] > y + costnou)
           {
               D[s][nodnou] = y + costnou;
               Q.push({D[s][nodnou] , nodnou});
           }
       }
    }
}

int main()
{
    cin >> cer >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        cin >> dr[i];
    for(int i = 1 ; i <= m ; ++i)
    {
        cin >> x >> y >> w;
        G[x].push_back({y , w});
        G[y].push_back({x , w});
    }
    if(cer == 1)
    {
        dfs(1 , dr[1] , s);
        cout << s;
    }
    else
    {
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
                D[i][j] = Inf;

        for(int i = 1 ; i <= n ; i++)
            dijkstra(i) , d[i] = D[1][i];

        /*for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= n ; j++)
                cout << D[i][j] << " ";
            cout << 'n';
        }*/

        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= n ; j++)
                if(d[i] > d[j] + D[j][i])
                    d[i] = d[j] + D[j][i];
        }
        cout << d[n];

    }
}