#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
    Info(int arg_to,int arg_cost){
        to = arg_to;
        cost = arg_cost;
    }
    int to;
    ll cost;
};

struct Data{
    Data(int arg_node_id,ll arg_sum_cost,ll arg_tmp_h){
        node_id = arg_node_id;
        sum_cost = arg_sum_cost;
        tmp_h = arg_tmp_h;
    }
    bool operator<(const struct Data &arg) const{
        return sum_cost > arg.sum_cost;
    };
    int node_id;
    ll sum_cost,tmp_h;
};

vector<Info> V[100001];
ll height[100001];
ll min_cost[100001];

int main(){

    int N,M;
    ll X;

    scanf("%d %d %lld",&N,&M,&X);

    for(int i = 1; i <= N; i++)scanf("%lld",&height[i]);

    int from,to;
    ll cost;

    for(int loop = 0; loop < M; loop++){
        scanf("%d %d %lld",&from,&to,&cost);
        V[from].push_back(Info(to,cost));
        V[to].push_back(Info(from,cost));
    }

    for(int i = 1; i <= N; i++){
        min_cost[i] = 999999999999999;
    }

    min_cost[1] = 0;

    priority_queue<Data> Q;
    Q.push(Data(1,0,X));

    ll ans = 999999999999999;
    ll next_loc,next_H;

    while(!Q.empty()){

        if(Q.top().node_id == N){
        	ans = min(ans,Q.top().sum_cost+height[N]-Q.top().tmp_h);
            Q.pop();
        }else if(Q.top().sum_cost > min_cost[Q.top().node_id]){
            Q.pop();
        }else{

            for(int i = 0; i < V[Q.top().node_id].size(); i++){

            	next_loc = Q.top().tmp_h-V[Q.top().node_id][i].cost;
            	next_H = height[V[Q.top().node_id][i].to];

                if(height[Q.top().node_id] < V[Q.top().node_id][i].cost)continue;

                if(next_loc >= 0 && next_loc <= next_H){

					if(min_cost[V[Q.top().node_id][i].to] > Q.top().sum_cost + V[Q.top().node_id][i].cost){
						min_cost[V[Q.top().node_id][i].to] = Q.top().sum_cost + V[Q.top().node_id][i].cost;
						Q.push(Data(V[Q.top().node_id][i].to,min_cost[V[Q.top().node_id][i].to],next_loc));
					}
                }else if(next_loc < 0){
                	if(min_cost[V[Q.top().node_id][i].to] > Q.top().sum_cost + V[Q.top().node_id][i].cost + abs(next_loc)){
						min_cost[V[Q.top().node_id][i].to] = Q.top().sum_cost + V[Q.top().node_id][i].cost+abs(next_loc);
						Q.push(Data(V[Q.top().node_id][i].to,min_cost[V[Q.top().node_id][i].to],0));
					}
                }else if(next_loc > next_H){
                	if(min_cost[V[Q.top().node_id][i].to] > Q.top().sum_cost + V[Q.top().node_id][i].cost + (next_loc-next_H)){
						min_cost[V[Q.top().node_id][i].to] = Q.top().sum_cost + V[Q.top().node_id][i].cost+(next_loc-next_H);
						Q.push(Data(V[Q.top().node_id][i].to,min_cost[V[Q.top().node_id][i].to],next_H));
					}
                }
            }
            Q.pop();
        }
    }

    if(min_cost[N] == 999999999999999){
        printf("-1\n");
        return 0;
    }else{
    	printf("%lld\n",ans);
    }

    return 0;
}

Measured memory_bytes: 23924