#include <bits/stdc++.h>
#define oo 1000000002

using namespace std;

int d[805];
int L[805][805];

int mx, n;
bool viz[805];
void df_1(int in, int putere) {
    mx = max(mx, d[in]);
    viz[in] = true;
    for(int i = 1; i <= n; i ++)
        if(L[in][i] && !viz[i] && L[in][i] <= putere)
            df_1(i, putere);
}

int mn = oo;
bool facut[805];

void dijkstra(int in, int prec) {
    facut[in] = true;
    int putere = d[in];
    int D[805];
    for(int i = 1; i <= n; i ++) D[i] = oo;
    D[in] = 0;
    vector<int> b;
    while(!b.empty()) b.pop_back();

    for(int i = 1; i <= n; i ++)
        if(L[in][i] && L[in][i] <= putere)
            b.push_back(i), D[i] = L[in][i];

    while(!b.empty()) {
        int MN = oo, poz = -1;
        for(int i = 0; i < b.size(); i ++) {
            if(MN > D[b[i]]) MN = D[b[i]], poz = i;
        }
        if(poz == -1) return ;

        int act = b[poz];
        b[poz] = b[b.size() - 1]; b.pop_back();
        for(int i = 1; i <= n; i ++) {
            if(L[act][i] && L[act][i] <= putere && D[i] > D[act] + MN)
                D[i] = D[act] + L[act][i], b.push_back(i);
        }
        if(d[act] > putere && !facut[act])
            dijkstra(act, prec + D[act]);
    }

    mn = min(mn, D[n] + prec);
}

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

    int t, m, A, B, D;
    f >> t >> n >> m;
    for(int i = 1; i <= n; i ++) f >> d[i];
    for(int i = 1; i <= m; i ++) {
        f >> A >> B >> D;
        L[A][B] = L[B][A] = D;
    }

    if(t == 1) {
        df_1(1, d[1]);
        g << mx << "\n";
        return 0;
    }

    dijkstra(1, 0);
    g << mn << "\n";
    return 0;
}