#include <bits/stdc++.h>
#define Nmax 850
#define INF (1 << 30)

using namespace std;

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

struct el {
    int cost, nod, dragon;
    bool operator <(const el &A) const {
        return cost > A.cost;
    }
};

int T, N, a[Nmax], dp[Nmax][Nmax], ans;
vector < pair <int, int> > L[Nmax];
priority_queue <el> q;
bool used[Nmax], vis[Nmax][Nmax];

inline void Read() {
    int M, i, x, y, c;
    fin >> T;
    fin >> N >> M;
    for (i = 1; i <= N; i++)
        fin >> a[i];
    for (i = 1; i <= M; i++) {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }
    fin.close();
}

inline void DFS(int nod, int dragon) {
    int nnod, cost;
    used[nod] = 1;
    for (auto it : L[nod]) {
        nnod = it.first;
        cost = it.second;
        if (!used[nnod] && dragon >= cost) {
            ans = max(ans, a[nnod]);
            DFS(nnod, dragon);
        }
    }
}

inline void Task_1() {
    ans = a[1];
    DFS(1, a[1]);
    fout << ans << "\n";
}

inline void Task_2() {
    int i, j, nod, cost, dragon, nnod, drg;
    el w, w1;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            dp[i][j] = INF;
    dp[1][1] = 0;
    w.nod = 1;
    w.cost = 0;
    w.dragon = 1;
    q.push(w);
    while (!q.empty()) {
        w = q.top();
        q.pop();
        nod = w.nod;
        dragon = w.dragon;
        drg = dragon;
        if(a[dragon] < a[nod])
            drg = nod;
        if (!vis[nod][drg]) {
            vis[nod][drg] = 1;
            for (auto it : L[nod]) {
                nnod = it.first;
                cost = it.second;
                if (a[drg] >= cost && dp[nnod][drg] > dp[nod][dragon] + cost) {
                    dp[nnod][drg] = dp[nod][dragon] + cost;
                    w1.nod = nnod;
                    w1.cost = dp[nnod][drg];
                    w1.dragon = drg;
                    q.push(w1);
                }
            }
        }
    }
    ans = dp[N][1];
    for (i = 2; i <= N; i++)
        ans = min(dp[N][i], ans);
    fout << ans << "\n";
}

inline void Solve() {
    if (T == 1)
        Task_1();
    else Task_2();
    fout.close();
}

int main() {
    Read();
    Solve();
    return 0;
}