#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("dragoni.in");
ofstream g("dragoni.out");

const int NMAX = 100005;
const int oo = (1 << 30);

vector < pair < int, int > > G[NMAX];

int P;
int N,M;
int DMax[NMAX];
int Dist[NMAX];
bool InCoada[NMAX];
bool Vizitat[NMAX];
int nodmax,putere;

struct Compara
{
    bool operator()(int x, int y)
    {
        return DMax[x] > DMax[y];
    }
};

priority_queue < int, vector < int >, Compara> Coada;

void Read()
{
    f >> P;
    f >> N >> M;
    for(int i = 1; i <= N; i++)
        f >> DMax[i];
    for(int i = 1; i <= M; i++)
    {
        int x,y,z;
        f >> x >> y >> z;
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }


}

void dfs1(int nod){
    Vizitat[nod] = true;
    for(unsigned int i = 0 ; i < G[nod].size();i++){
        int Vecin = G[nod][i].first;
        int Cost = G[nod][i].second;
        if(!Vizitat[Vecin] && Cost <= putere){
            if(nodmax < DMax[Vecin]){
                nodmax = DMax[Vecin];
            }
            dfs1(Vecin);
        }
    }
}

void Dijkstra(int nodStart)
{
    for(int i = 1; i <= N; i++)
        Dist[i] = oo;
    Dist[1] = 0;
    Coada.push(nodStart);
    InCoada[nodStart] = true;
    int DistantaDragonNod = DMax[nodStart];
    while(!Coada.empty())
    {
        int nodCurent = Coada.top();
        Coada.pop();
        InCoada[nodCurent] = false;
        for(unsigned int i = 0; i < G[nodCurent].size(); i++)
        {
            //cout << DistantaDragonNod << " ";
            int Vecin = G[nodCurent][i].first;
            int Cost = G[nodCurent][i].second;
            int DistantaDragonVecin = DMax[Vecin];
            if(Dist[nodCurent] + Cost < Dist[Vecin]   && DistantaDragonNod >= Cost)
            {
                Dist[Vecin] = Dist[nodCurent] + Cost;
                 if(DistantaDragonNod < DistantaDragonVecin)
                    DistantaDragonNod = DistantaDragonVecin;
                if(InCoada[Vecin] == false)
                {
                    Coada.push(Vecin);
                    InCoada[Vecin] = true;
                }
            }
        }

    }
}

 void P1(){
    putere = DMax[1];
    nodmax = -1;
    dfs1(1);
    g << nodmax;

 }

 void P2(){
    Dijkstra(1);
    g << Dist[N];
 }

int main()
{
    Read();
    if(P == 1)
        P1();
    else P2();


    return 0;
}