#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e4+10;
const int M=1e5+10;
int n,m,mxHP;
int hp[N];

struct edge{
	int to,nxt,w;
}e[M<<1];

int hd[N],nE=0;

void addedge(int u,int v,int w){
	e[++nE]=(edge){v,hd[u],w};
	hd[u]=nE;
}

int lstHP[N],nowHP[N];
bool in[N];
struct node{
	int u,d;
};
queue<node> q;
void SPFA(){
	lstHP[1]=nowHP[1]=mxHP;in[1]=1;
	q.push((node){1,0});
	int lstD=0;
	
	while(!q.empty()){
		int u=q.front().u,d=q.front().d;q.pop();in[u]=0;
		if(u==n){
			printf("%d\n",d);
			return;
		}
		if(d!=lstD){
			memset(in,0,sizeof(in));
			for(int i=1;i<=n;i++)nowHP[i]=lstHP[i];
		}
		for(int i=hd[u];i;i=e[i].nxt){
			int v=e[i].to;
			int w=e[i].w;
			int t=min(mxHP,nowHP[u]-w+hp[v]);
			if(nowHP[u]>w&&lstHP[v]<t){
				lstHP[v]=t;
				if(!in[v]){
					in[v]=1;
					q.push((node){v,d+1});
				}
			}
		}
		lstD=d;
	}
	
	printf("-1\n");
}

int main(){
	
	scanf("%d %d %d",&n,&m,&mxHP);
	
	for(int i=1;i<=n;i++)scanf("%d",&hp[i]);
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}	
	
	SPFA();
	
	return 0;
}