#include <fstream>
#include <vector>
#define INF 2000000000
using namespace std;
ifstream fin("dragoni.in");
ofstream fout("dragoni.out");
vector< pair<short, int> > g[810];
short n, m, x, y, p, u;
int d, rez=INF, curent;
short insula[810];
int dist[810][810];
bool viz[810];
short coada[50000];

void dfs(int nod)
{
    if(nod==n)
    {
        if(curent<rez)
            rez=curent;
        return;
    }
    viz[nod]=1;

    for(int i=1; i<=n; i++)
        if(!viz[i])
        if(dist[nod][i]!=INF)
    {
        curent+=dist[nod][i];
        dfs(i);
        curent-=dist[nod][i];
    }

    viz[nod]=0;
}

void BellmanFord(int nod)
{
    for(int i=1;i<=n;i++)
        viz[i]=0;

    p=u=1;
    coada[1]=nod;
    while(p<=u)
    {
        viz[coada[p]]=0;

        for(int i=0; i<g[coada[p]].size(); i++)
            if(g[coada[p]][i].second<=insula[nod])
            if(dist[nod][coada[p]] + g[coada[p]][i].second < dist[nod][g[coada[p]][i].first])
        {
            if(!viz[g[coada[p]][i].first])
            {
            coada[++u]=g[coada[p]][i].first;
            viz[g[coada[p]][i].first]=1;
            }

            dist[nod][g[coada[p]][i].first]=dist[nod][coada[p]]+g[coada[p]][i].second;
        }
        p++;
    }
}

void caz1()
{
    int rez=0;

    p=u=1;
    coada[1]=1;
    while(p<=u)
    {
        if(rez<insula[coada[p]])
            rez=insula[coada[p]];

        for(int i=0; i<g[coada[p]].size(); i++)
            if(!viz[g[coada[p]][i].first])
            if(g[coada[p]][i].second<=insula[1])
        {
            coada[++u]=g[coada[p]][i].first;
            viz[g[coada[p]][i].first]=1;
        }
        p++;
    }

    fout<<rez;
}

void caz2()
{
    for(int i=1; i<n; i++)
        for(int j=1;j<=n;j++)
        if(i!=j)
        dist[i][j]=INF;

    BellmanFord(1);
    for(int i=1;i<n;i++)
        if(insula[i]>insula[1])
        BellmanFord(i);
/*
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=n;j++)
            fout<<dist[i][j]<<' ';
        fout<<'\n';
    }
*/
    for(int i=1;i<=n;i++)
        viz[i]=0;

    dfs(1);

    fout<<rez;
}

int main()
{
    fin>>p;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>insula[i];
    for(int i=1;i<=m;i++)
        {
            fin>>x>>y>>d;
            g[x].push_back(make_pair(y, d));
            g[y].push_back(make_pair(x, d));
        }

    if(p==1)
        caz1();
    else
        caz2();

    return 0;
}