#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

ifstream f("coach.in");
ofstream g("coach.out");

const int maxn = 105, maxm = 5005, inf = 1 << 30;

struct xy {
    int x, y;
};

vector <xy> v[maxn];
int best[maxn];
int n, m, t;
int a[maxn];
class time {
public:
    bool operator () (int x, int y) {
        return best[x] > best[y];
    }
};
priority_queue <int, vector<int>, time> q;

int dij(int start, int finish, int minc, int maxc) {
    while(!q.empty())
        q.pop();
    q.push(start);
    //memset(best, inf, sizeof(best));
    for(int i = 1; i <= n; i ++)
        best[i] = inf;
    best[start] = 0;
    /*
    for(int i = 1; i <= n; i ++)
        g << best[i] << ' ';
    g << '\n';
    */
    while(!q.empty()) {
        int x = q.top();
        //g << x << '\n';
        q.pop();
        if(x == finish) {
            return best[x];
        }
        for(auto u : v[x]) {
            //g << ' ' << u.x << ' ' << best[u.x] << ' ' << (best[u.x] != 0 && a[u.x] >= minc && a[u.x] <= maxc) << '\n';
            if(u.x != start && best[u.x] != 0 && a[u.x] >= minc && a[u.x] <= maxc) {
                //g << ' ' << u.x << '\n';
                if(best[u.x] == inf)
                    q.push(u.x);
                if(best[x] + u.y < best[u.x]) {
                    best[u.x] = best[x] + u.y;
                }
            }
        }
    }
    return -1;
}

int main()
{
    int i, x, y, z;

    f >> n >> m >> t;
    for(i = 1; i <= n; i ++) {
        f >> a[i];
    }
    for(i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    g << dij(3, 6, 20, 55) << '\n';

    f.close();
    g.close();
    return 0;
}