#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

enum Type{
	COLD,
	MID,
	HOT,
};

struct Info{
	Info(int arg_node_id,int arg_sum_time,int arg_rest,Type arg_pre_type){
		node_id = arg_node_id;
		sum_time = arg_sum_time;
		rest = arg_rest;
		pre_type = arg_pre_type;
	}
	int node_id,sum_time,rest;
	Type pre_type;
};

struct Data{
	Data(int arg_to,int arg_cost){
		to = arg_to;
		cost = arg_cost;
	}
	int to,cost;
};

int dp[3][10000][201];
Type room_info[10000],type_array[3] = {COLD,MID,HOT};


int main(){

	int N,M,X;
	scanf("%d %d %d",&N,&M,&X);

	int tmp;
	for(int i = 0; i < N; i++){
		scanf("%d",&tmp);
		room_info[i] = type_array[tmp];
	}

	vector<Data> V[N];

	int from,to,cost;

	for(int i = 0; i < M; i++){
		scanf("%d %d %d",&from,&to,&cost);
		from--;
		to--;
		V[from].push_back(Data(to,cost));
		V[to].push_back(Data(from,cost));
	}

	for(int i = 0; i <= N-1; i++){
		for(int k = 0; k <= X; k++){
			dp[COLD][i][k] = BIG_NUM;
			dp[MID][i][k] = BIG_NUM;
			dp[HOT][i][k] = BIG_NUM;
		}
	}

	queue<Info> Q;
	dp[COLD][0][X] = 0;
	Q.push(Info(0,0,X,COLD));

	int ans = BIG_NUM,next_node,next_rest;

	while(!Q.empty()){

		if(Q.front().node_id == N-1){
			ans = min(ans,Q.front().sum_time);
			Q.pop();
		}else if(Q.front().sum_time > dp[Q.front().pre_type][Q.front().node_id][Q.front().rest]){
			Q.pop();
		}else{

			for(int i = 0; i < V[Q.front().node_id].size(); i++){
				next_node = V[Q.front().node_id][i].to;

				if(room_info[next_node] == MID){
					next_rest = max(0,Q.front().rest-V[Q.front().node_id][i].cost);

					if(next_rest > 0){

						if(dp[Q.front().pre_type][next_node][next_rest] > Q.front().sum_time+V[Q.front().node_id][i].cost){
							dp[Q.front().pre_type][next_node][next_rest] = Q.front().sum_time+V[Q.front().node_id][i].cost;
							Q.push(Info(next_node,dp[Q.front().pre_type][next_node][next_rest],next_rest,Q.front().pre_type));
						}
					}else{ //next_rest == 0
						if(dp[MID][next_node][0] > Q.front().sum_time+V[Q.front().node_id][i].cost){
							dp[MID][next_node][0] = Q.front().sum_time+V[Q.front().node_id][i].cost;
							Q.push(Info(next_node,dp[MID][next_node][0],0,MID));
						}
					}
				}else{

					if(Q.front().pre_type == MID){
						if(dp[room_info[next_node]][next_node][X] > Q.front().sum_time+V[Q.front().node_id][i].cost){
							dp[room_info[next_node]][next_node][X] = Q.front().sum_time+V[Q.front().node_id][i].cost;
							Q.push(Info(next_node,dp[room_info[next_node]][next_node][X],X,room_info[next_node]));
						}
					}else{

						if(Q.front().pre_type == room_info[next_node]){
							if(dp[room_info[next_node]][next_node][X] > Q.front().sum_time+V[Q.front().node_id][i].cost){
								dp[room_info[next_node]][next_node][X] = Q.front().sum_time+V[Q.front().node_id][i].cost;
								Q.push(Info(next_node,dp[room_info[next_node]][next_node][X],X,room_info[next_node]));
							}
						}else{ //Q.front().pre_type != room_info[next_node]
							if(V[Q.front().node_id][i].cost < Q.front().rest)continue;

							if(dp[room_info[next_node]][next_node][X] > Q.front().sum_time+V[Q.front().node_id][i].cost){
								dp[room_info[next_node]][next_node][X] = Q.front().sum_time+V[Q.front().node_id][i].cost;
								Q.push(Info(next_node,dp[room_info[next_node]][next_node][X],X,room_info[next_node]));
							}

						}
					}
				}
			}
			Q.pop();
		}
	}

	printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 28088