#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e4 + 10;

int n, m, p;

int a[maxn];

struct Edge{
	int v, w;
};

vector<Edge> G[maxn];

map<int, int> dis[maxn];
map<int, bool> vis[maxn];

struct Point{
	int u, w, hp;
};

bool operator > (const Point &a, const Point &b) {
	return a.w > b.w;
}

int ans = -1;

void dij(int s) {
	priority_queue<Point, vector<Point>, greater<Point> > que;
	dis[s][p] = 0;
	que.push({s, 0, p});
	while (!que.empty()) {
		auto tmp = que.top();
		que.pop();
		int u = tmp.u, hp = tmp.hp;
		if (vis[u].count(hp)) {
			continue;
		}
		vis[u][hp] = 1;
		for (auto tmp: G[u]) {
			int v = tmp.v, w = tmp.w;
			if (hp - w > 0 && (!dis[v].count(min(p, hp-w+a[v])) || dis[v][min(p, hp-w+a[v])] > dis[u][hp] + 1)) {
				dis[v][min(p, hp-w+a[v])] = dis[u][hp] + 1;
				que.push({v, dis[v][min(p, hp-w+a[v])], min(p, hp-w+a[v])});
				if (v == n) {
					ans = dis[v][min(p, hp-w+a[v])];
					return;
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> p;
	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});
	}
	
	dij(1);
	
	cout << ans << endl;
}

/*

5 5 3
3 2 3 2 3
1 5 4
1 2 1
2 3 2
3 4 1
4 5 2

*/

answer.code: In function 'void dij(int)':
answer.code:33:10: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
  que.push({s, 0, p});\x0d
          ^
answer.code:33:20: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
  que.push({s, 0, p});\x0d
                    ^
answer.code:35:8: error: 'tmp' does not name a type
   auto tmp = que.top();\x0d
        ^
answer.code:37:11: error: 'tmp' was not de...