#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

struct E{
	int to,d;
};
struct E2{
	int to,state,d;
	long long int time;
	bool operator<(const E2& e2)const{
		return time>e2.time;
	}
};


long long int dp[4][203][10003];
int room[10003];
vector<E> cons[10003];
int n,m,x;
int main() {
	memset(dp,-1,sizeof(dp));
	cin>>n>>m>>x;
	for(int i=1;i<=n;i++){
		cin>>room[i];
	}
	for(int i=0;i<m;i++){
		int from,to;
		E e1;
		cin>>from>>to>>e1.d;
		e1.to=to;
		cons[from].push_back(e1);
		e1.to=from;
		cons[to].push_back(e1);
	}
	E2 e2;
	e2.to=1;
	e2.state=room[1];
	e2.time=0;
	e2.d=x;
	priority_queue<E2> pq;
	pq.push(e2);
	while(pq.size()>0){
		E2 e2=pq.top();
		cout<<"("<<e2.time<<" "<<e2.state<<" "<<e2.to<<" "<<e2.d<<")"<<endl;
		pq.pop();
		long long int t1=dp[e2.state][e2.d][e2.to];
		if(t1!=-1 && t1<=e2.time)continue;
		dp[e2.state][e2.d][e2.to]=e2.time;
		for(auto it=cons[e2.to].begin();it!=cons[e2.to].end();it++){
			E e1a=(*it);
			
			E2 e2a;
			e2a.to=e1a.to;
			e2a.state=e2.state;
			e2a.time=e2.time+e1a.d;
			
			if(room[e2.to]==1){
				e2a.d=e2.d-e1a.d;
			}else{
				e2a.d=x-e1a.d;
			}
			cout<<"("<<e1a.to<<" "<<e1a.d<<" "<<e2a.d<<")";
			bool moveok=false;
			if(e2a.d<=0){
				e2a.d=0;
				e2a.state=room[e1a.to];
				moveok=true;
			}else if(room[e1a.to]==1){
				moveok=true;
			}else if(e2a.state=room[e1a.to]){
				moveok=true;
			}
			if(moveok==false)continue;
			pq.push(e2a);
		}
		cout<<endl;
	}
	int ans=-1;
	for(int i=0;i<=200;i++){
		long long int t1=dp[room[n]][i][n];
		if(ans==-1 || (t1!=-1 && t1<ans))ans=t1;
	}
	cout<<ans;
	return 0;
}