#include<bits/stdc++.h>
using namespace std;
int n, m, k, head[30004], nxt[200005], to[200005], w[200005], ccnt, a[30004], u[30004], v[30004], ins[30004];
struct node {
	int p, w;
};
inline void add(int p, int q, int ww) {
	nxt[++ccnt] = head[p];
	to[ccnt] = q;
	w[ccnt] = ww;
	head[p] = ccnt;
}
queue<node> que;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	int p, q, ww;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> p >> q >> ww;
		add(p, q, ww);
		add(q, p, ww);
	}
	node op;
	int lst = 0;
	v[1] = u[1] = k;
	op.p = 1;
	op.w = 0;
	ins[0] = true;
	que.push(op);
	while (que.size()) {
		op = que.front();
		if (op.p == n) {
			cout << op.w;
			return 0;
		}
		if (op.w != lst) {
			for (int i = 1; i <= n; i++) {
				u[i] = v[i];
				ins[i] = false;
			}
		}
		for (int i = head[op.p]; i; i = nxt[i]) {
			if (u[op.p] > w[i]) {
				if (min(u[op.p] - w[i] + a[to[i]], k) > v[to[i]]) {
					v[to[i]] = min(u[op.p] - w[i] + a[to[i]], k);
					if (!ins[to[i]]) {
						que.push(node{to[i], op.w + 1});
						ins[to[i]] = true;
					}
				}
			}
		}
		lst = op.w;
		que.pop();
	}
	cout << -1;
	return 0;
}