#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dragoni.in");
ofstream fout("dragoni.out");
const int NMAX = 805;
vector < pair<int,int> > G[NMAX];
int P[NMAX],n,D[NMAX];
bitset < NMAX > V;
set < pair < int ,int > > T;
void bfs()
{
    int nod;
    T.insert({0,1});
    while(!T.empty()){
        nod = (*T.begin()).second;
        T.erase(*T.begin());
        for(int i = 0; i < G[nod].size(); i++){
            if(D[G[nod][i].second] < D[nod] + G[nod][i].first && P[1] >= G[nod][i].first && V[G[nod][i].second] == 0){
                 D[G[nod][i].second] = D[nod] + G[nod][i].first;
                 V[G[nod][i].second] = 1;
                 T.insert({D[G[nod][i].second],G[nod][i].second});
            }
        }
    }
}
int main()
{
    int p,m,x,y,c;
    fin >> p;
    if(p == 1){
        fin >> n >> m;
        for(int i = 1; i <= n; i++)
            fin >> P[i];
        for(int i = 1; i <= m; i++){
            fin >> x >> y >> c;
            G[x].push_back({c,y});
            G[y].push_back({c,x});
        }
        bfs();
        int mx = 0;
        for(int i = 1; i <= n; i++)
            if(D[i] != 0 && P[i] > mx)
            mx = P[i];
        fout << mx;
    }
    return 0;
}