#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int N,M,X;
int H[100000];
vector<pair<int,int> > tonari[100000];
map<int,LL> dp[100000];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

	cin >> N >> M >> X;
    for(int i=0; i<N; i++) cin >> H[i];
    for(int i=0; i<M; i++){
        int A,B,T;
        cin >> A >> B >> T;
        A--; B--;
        tonari[A].push_back(MP(B, T));
        tonari[B].push_back(MP(A, T));
    }

    dp[0][X] = 0;
    LL ans = LL_MAX;
    priority_queue<pair<LL,pair<pair<int,int>,int> > > que;
    que.push(MP(LL_MAX,MP(MP(0,X),0)));
    while(!que.empty()){
        LL c = LL_MAX - que.top().first;
        int now = que.top().second.first.first;
        int h = que.top().second.first.second;
        int old = que.top().second.second;
        que.pop();
        if(dp[now].count(h) == 0 || dp[now][h] != c || c >= ans) continue;
        //cout << now << " " << h << " " << c << endl;

        for(int i=0; i<tonari[now].size(); i++){
            int tmp = tonari[now][i].first;
            int t = tonari[now][i].second;
            if(tmp == old) continue;
            //cout << tmp << " " << t << endl;
            int result;
            if(h-t < 0){
                if(H[now]-t < 0) continue;
                LL nc = (t-h) + t;
                if(dp[tmp].count(0) != 0 && dp[tmp][0] <= c + nc) continue;
                dp[tmp][0] = c + nc;
                result = 0;
            }
            else if(h-t > H[tmp]){
                LL nc = h - (H[tmp] + t) + t;
                if(dp[tmp].count(H[tmp]) != 0 && dp[tmp][H[tmp]] <= c + nc) continue;
                dp[tmp][H[tmp]] = c + nc;
                result = H[tmp];
            }
            else{
                LL nc = t;
                if(dp[tmp].count(h-t) != 0 && dp[tmp][h-t] <= c + nc) continue;
                dp[tmp][h-t] = c + nc;
                result = h-t;
            }

            LL memo = dp[tmp][result];
            auto itr = dp[tmp].lower_bound(result);
            if(itr != dp[tmp].begin()) itr--;
            int oldH = itr->first;
            LL oldC = itr->second;
            itr++;
            while(itr != dp[tmp].end()){
                if(oldC+abs(itr->first - oldH) <= itr->second){
                    int k = itr->first;
                    itr--;
                    dp[tmp].erase(k);
                    //cout << "erase1:" << k << endl;
                }
                oldH = itr->first;
                oldC = itr->second;
                itr++;
            }

            itr = dp[tmp].upper_bound(result);
            if(itr == dp[tmp].end()) itr--;
            oldH = itr->first;
            oldC = itr->second;
            while(itr != dp[tmp].begin()){
                itr--;
                if(oldC+abs(itr->first - oldH) <= itr->second){
                    int k = itr->first;
                    itr++;
                    dp[tmp].erase(k);
                    //cout << "erase2:" << k << endl;
                }
                oldH = itr->first;
                oldC = itr->second;
            }

            if(dp[tmp].count(result) != 0){
                que.push(MP(LL_MAX-memo, MP(MP(tmp, result),now)));
                if(tmp == N-1) ans = min(ans, memo + H[N-1] - result);
            }
        }
    }

    if(ans == LL_MAX) cout << -1 << endl;
    else cout << ans << endl;

	return 0;
}


Measured memory_bytes: 26132