#include <bits/stdc++.h>
#define C__ const
#define int long long
using namespace std;
C__ int N_ = 3e4 + 10, inf = 0x3f3f3f3f3f3f3f3fLL;
int n, m, k, a[N_];
vector<pair<int, int> > g[N_];
bool inq[N_];
set<pair<int, int> > res[N_];
int SPFA() {
	int ans = inf;
	queue<int> que;
	inq[1] = true, res[1].insert({k, 0}), que.push(1);
	while (!que.empty()) {
		int u = que.front(); que.pop(); inq[u] = false;
		for (pair<int, int> P : res[u]) {
			int hel = P.first, dis = P.second;
			if (u == n && hel > 0) ans = min(ans, dis);
			hel += a[u], hel = min(hel, k);
			for (pair<int, int> P : g[u]) {
				int v = P.first, w = P.second;
				if (hel - w > 0) {
					res[v].insert({hel - w, dis + 1});
					if (!inq[v]) inq[v] = true, que.push(v);
				}
			}
		}
		res[u].clear();
	}
	return ans;
}
signed 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});
	}
	cout << SPFA() << "\n";
	return 0;
}


/*
int bfs() {
int ans = inf;
queue<tuple<int, int, int> > que;
inq[1] = true, que.push({1, k, 0});
while (!que.empty()) {
auto [u, hel, dis] = que.front(); que.pop();
if (u == n && hel > 0) ans = min(ans, dis);
hel += a[u], hel = min(hel, k);
for (auto [v, w] : g[u]) {
if (hel - w > 0) que.push({v, hel - w, dis + 1});
}
}
return ans;
}
*/