#include <fstream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

#define Mx32 1000000010

ifstream fin("dragoni.in");
ofstream fout("dragoni.out");

int n,m,speci[810],x,y,parcurs,ds,mix=Mx32,p,i,nod,Min=0,dismin[810],dramax[810],combustibil;
bool viz[810];
vector< pair <int,int> > l[50010];
queue<int> coada;
priority_queue< pair < int,pair < int,int > > , vector < pair < int,pair < int,int > > > , greater < pair < int,pair < int,int > > > > qu;

void dijkstr_simplu()
{
    coada.push(1);
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        if(viz[nod]==0)
        {
            viz[nod]=1;
            for(int i=0;i<l[nod].size();++i)
            {
                if(combustibil>=l[nod][i].second && viz[l[nod][i].first]==0)
                {
                    if(speci[l[nod][i].first]>Min)
                        Min=speci[l[nod][i].first];
                    coada.push(l[nod][i].first);
                }
            }
        }
    }
}

void big_dijkstra()
{
    qu.push({0,{1,speci[1]}});

    for(i=2;i<=n;++i)
        dismin[i]=Mx32;
    dramax[1]=speci[1];

    while(!qu.empty())
    {
        nod=qu.top().second.first;
        combustibil=qu.top().second.second;
        parcurs=qu.top().first;
        qu.pop();

        combustibil=max(speci[nod],combustibil);

        for(int i=0;i<l[nod].size();++i)
        {
            if(combustibil>=l[nod][i].second)
            {

                if(combustibil>dramax[l[nod][i].first] || dismin[l[nod][i].first]>parcurs+l[nod][i].second)
                {
                    dismin[l[nod][i].first]=min(dismin[l[nod][i].first],parcurs+l[nod][i].second);
                    dramax[l[nod][i].first]=max(dramax[l[nod][i].first],combustibil);
                    qu.push({parcurs+l[nod][i].second,{l[nod][i].first,combustibil}});
                }
            }
        }
    }

}

int main()
{
    fin>>p;
    fin>>n>>m;
    for(i=1;i<=n;++i)
    {
        fin>>speci[i];
    }
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>ds;
        l[x].push_back({y,ds});
        l[y].push_back({x,ds});
    }
    combustibil=speci[1];
    if(p==1)
    {
        dijkstr_simplu();
        fout<<Min;
    }
    else
    {
        big_dijkstra();
        /*for(int i=1;i<=n;++i)
            fout<<dismin[i]<<" "<<dramax[i]<<"\n";*/
        fout<<dismin[n];
    }
    return 0;
}