#include<bits/stdc++.h>
using namespace std;
int mn_cost[30005],c1[30005];
bool in[30005];int a[200005];
int n,m,k;
vector<pair<int,int> >p[300005];
signed main(){
	cin >> n >> m >> k;
	for(int i = 1;i<=n;i++)cin >> a[i];
	for(int i = 1;i<=m;i++){
		int a,b,c;cin >>a  >> b >> c;
		p[a].push_back({b,c}),p[b].push_back({a,c});
	}
	c1[1] = mn_cost[1] =k;in[1] = 1;
	queue<pair<int,int> >q;q.push({1,0});int lst = 0;
	while(!q.empty()){
		int now = q.front().first,d = q.front().second;q.pop();
		if(now == n){
			cout << d << endl;return 0;
		}if(d!=lst){
			memset(in,0,sizeof(in));
			for(int i = 1;i<=n;i++)mn_cost[i] = c1[i];
		}for(int i =0;i<p[now].size();i++){
			int to = p[now][i].first,co = p[now][i].second,t = min(k,mn_cost[now]-co+a[to]);
			if(mn_cost[now]>co and c1[to]<t){
				c1[to] = t;
				if(!in[to]){
					in[to] = 1;
					q.push({to,d+1});
				}
			}
		}lst = d;
	}cout << -1 << endl;
	return 0;
}