// Problem: B. 小游戏
// Contest: undefined - NOIP2024训练赛 02
// URL: http://noi.ac/contest/1154/problem/2058
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read(){
int xx = 0, ff = 1;char ch = getchar();
while (ch < '0' || ch > '9'){
if (ch == '-')ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
struct Node{
int v,w;
};vector<Node> e[N];
int d[N],g[N];
int n,m,V;
int w[N];
void add(int c,int b,int a){
e[a].pb({b,c});
e[b].pb({a,c});
}
queue<int> q;
void spfa(){
memset(d,0x3f3f,sizeof d);
d[1]=0;
g[1]=V;
q.push(1);
while(q.size()){
int x=q.front();
q.pop();
if(x==n){
cout<<d[x];;
return ;
}
for(auto v:e[x]){
if(g[v.v]>=min(V,g[x]-v.w+w[v.v])||g[x]-v.w<=0)continue;
g[v.v]=min(V,g[x]-v.w+w[v.v]);
d[v.v]=d[x]+1;
q.push(v.v);
}
}
}
signed main(){
n=rd,m=rd,V=rd;
for(int i=1;i<=n;i++){
w[i]=rd;
}
for(int i=1;i<=m;i++){
add(rd,rd,rd);
}
spfa();
}
