#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

struct edge{
	int v, w;
};

int N, M, MAXN, ans = 0x3f3f3f3f;
int dis[2000006];
bool vis[2000006];
vector<edge> tmp[100005];
vector<int> E[2000006];
int val[100005];
int u[200005], v[200005], w[200005];

void dijkstra(int st){
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[st] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
	q.push({0, st});
	while (!q.empty()){
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		// cout << u << " " << dis[u] << ";;\n";
		vis[u] = 1;
		for (auto && v : E[u]){
			if (dis[v] <= dis[u] + 1) continue;
			dis[v] = dis[u] + 1;
			q.push({dis[v], v});
		}
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("../data.in", "r", stdin);
	freopen("../data.out", "w", stdout);
#endif

	scanf("%d %d %d", &N, &M, &MAXN);
	for (int i = 1; i <= N; i ++){
		scanf("%d", &val[i]);
	}
	for (int i = 1; i <= M; i ++){
		scanf("%d %d %d", &u[i], &v[i], &w[i]);
		tmp[u[i]].push_back({v[i], w[i]});
		tmp[v[i]].push_back({u[i], w[i]});
	}
	for (int k = 1; k <= MAXN; k ++){
		for (int i = 1; i <= N; i ++){
			for (auto && v : tmp[i]){
				if (k - v.w <= 0) continue;
				E[k * N + i].push_back(min(MAXN, k - v.w + val[v.v]) * N + v.v);
			}
		}
	}
	dijkstra(MAXN * N + 1);
	for (int k = 1; k <= MAXN; k ++){
		ans = min(ans, dis[k * N + N]);
	}
	if (ans == 0x3f3f3f3f) ans = -1;
	printf("%d\n", ans);
	
	return 0;
}