#include<bits/stdc++.h>
using namespace std;
#define y1 y114514
#define ll long long
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define per(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define vpii vector<pair<int,int>>
#define mk make_pair
#define MAX 0x7fffffff
#define popcount __builtin_popcountll
#define TIME 1e3*clock()/CLOCKS_PER_SEC
#define ckmax(x,y) x=x<y?y:x
#define ckmin(x,y) x=x<y?x:y
inline ll rd() {
	ll x = 0, flag = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return x * flag;
}
inline void wr(ll x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) wr(x / 10);
	putchar(x % 10 + '0');
}
bool Mbe;

const int N = 3e4 + 5;
int n, m, hp, a[N], vis[N];
vpii e[N];
struct node {
	int u, h, dis;
};
queue<node> q;

bool Med;
signed main() {
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> hp;
	rep(i, 1, n) cin >> a[i];
	rep(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].pb(mk(v, w));
		e[v].pb(mk(u, w));
	}
	q.push((node) {
		1, hp, 0
	});
	while (q.size()) {
		node x = q.front();
		q.pop();
		int u = x.u, h = x.h, dis = x.dis;
		for (auto y : e[u]) {
			int v = y.fi, w = y.se;
			if (h - w > 0) {
				w = min((h - w + a[v]), hp);
				if (w > vis[v]) {
					vis[v] = w;
					q.push((node) {
						v, w, dis + 1
					});
					if (v == n) {
						cout << dis + 1;
						return 0;
					}
				}
			}
		}
	}
	cout << -1;

	return cerr << "Time: " << TIME << " ms\n", 0;
}