#include <bits/stdc++.h>
#define C__ const
using namespace std;
C__ int N_ = 3e4 + 10;
int n, m, k, a[N_], b[N_];
vector<pair<int, int> > g[N_];
struct triple { int x, y, z; };
int SPFA() {
	queue<triple> que;
	que.push({1, k, 0});
	while (!que.empty()) {
		auto ___ = que.front(); que.pop();
		int u = ___.x, hel = ___.y, dis = ___.z;
		if (u == n) return dis;
		for (auto ___ : g[u]) {
			int v = ___.first, w = ___.second;
			if (hel - w <= 0) continue;
			int nex = min(k, hel - w + a[v]);
			if (nex <= b[v]) continue;
			que.push({v, nex, dis + 1});
			b[v] = nex;
		}
	}
	return -1;
}
int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	cout << SPFA() << "\n";
	return 0;
}