#include <bits/stdc++.h>
using namespace std;
#define F(i,x,y) for (int i = x; i <= y; i ++ )
#define D(i,x,y) for (int i = x; i >= y; i -- )
#define E(i,u) for (auto &i : u)
#define u first
#define v second
#define pii pair<int,int>
const int N = 3e4 + 10, M = 1e5 + 10;
#define int long long
int n, m, hpM, a[N];
vector<pii> G[N];
bool flag = false;
bool vis[N];
void dfs(int now, int hp, int depth, int maxD)
{
	if (depth > maxD) return;
	if (flag) return;
	if (now == n)
		return flag = true, void();
	hp = min(hpM,hp + a[now]); 
//	vis[now] = 1;
	E(t, G[now])
	{
		auto u = t.u, w = t.v;
//		if (vis[u]) continue;
		if (hp - w < 0) continue;
		if (maxD == 10)
			cout << now << "->" << u << '\n';
		dfs(u, hp - w, depth + 1, maxD);
		if (flag) return;
	}
 } 
void koishi()
{
	cin >> n >> m >> hpM;
	F(i,1,n) cin >> a[i];
	F(i,1,m) 
	{
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	int l = m - 1, r = m*(m - 1)/2 + 1, mid = 0;
	while (l + 1 < r)
	{
		mid = (l + r) >> 1;
		dfs(1, hpM, 0, mid);
		if (flag) r = mid;
		else l = mid;
		flag = false;
//		memset(vis, 0, sizeof vis);
	}
	cout << l;
}
#undef int
int main()
{
	cin.tie(nullptr) -> sync_with_stdio(false);
	koishi();
	return 0;
}

answer.code: In function 'void dfs(long long int, long long int, long long int, long long int)':
answer.code:23:4: error: ISO C++ forbids declaration of 't' with no type [-fpermissive]
  E(t, G[now])\x0d
    ^
answer.code:5:27: note: in definition of macro 'E'
 #define E(i,u) for (auto &i : u)\x0d
                           ^
answer.code:23:7: error: range-based 'for' loops are not allowed in C++98 mode
  E(t, G[now])\x0d
       ^
answer.code:5:31: note: in definition of macro 'E'
 #define E(i,u) for (au...