#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

const int N = 3e4 + 5;

int n, m; // 点数、血量上限
int hp[N];

struct node {
	int v, d; // 目标点、据起点距离 
	int bl; // 血量 
}; 

map <PII, bool> vis; // 目标点，剩余血量
map <PII, int> dis;

struct cmp {
	bool operator()(node a, node b) {
		return a.d > b.d;
	}
};

priority_queue <node, vector <node>, cmp> q;
vector <PII> e[N];

void BFS(int s) {
	dis[{s, m}] = 0;
	//vis[{s, m}] = 1;
	q.push({s, 0, m});
	while (q.size()) {
		int u = q.top().v, bl = q.top().bl;
		//cout << u << " " << bl << "\n";
		if (u == n) {
			cout << q.top().d;
			exit(0);
		}
		q.pop();
		if (vis[{u, bl}]) continue;
		vis[{u, bl}] = 1;
		
		//cout << u << " " << bl << " " << dd << "\n";
		
		for (auto to : e[u]) {
			int p = min(bl + hp[u], m) - to.second;
			if (p <= 0) continue;
			int v = to.first;
			if (dis[{v, p}] > dis[{u, bl}] + 1 || !dis[{v, p}]) {
				dis[{v, p}] = dis[{u, bl}] + 1;
				q.push({v, dis[{v, p}], p});
			}
		}
		
	}
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(0);
	int E; cin >> n >> E >> m;
	for (int i = 1; i <= n; i++) cin >> hp[i];
	while (E--) {
		int x, y, z; cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	BFS(1);
} 

answer.code: In function 'void BFS(long long int)':
answer.code:29:5: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
  dis[{s, m}] = 0;\x0d
     ^
answer.code:29:12: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
  dis[{s, m}] = 0;\x0d
            ^
answer.code:31:8: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
  q.push({s, 0, m});...