#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//????????????????????????????????????
#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const ll inf = 4523372036854775807;
const ld pi = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899;
struct H {
	int x, y;
};
struct P {
	int pos, cost, deg, time;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//??£??\???????????¨???
	ll to, cost;
};
struct S {//???????????±?????\???????????°
	int from, to, cost;
};
ll gcm(ll i, ll j) {//?????§??¬?´???°
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(ld a, ld b, ld c, ld d) {
	return sqrt(pow(a - c, 2) + pow(b - d, 2));
}//rad?????§?¨???????2??????????????¢
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
int n, m, x;
int a[10001][3][201];
int b[10001];
vector<B>e[20000];
signed main() {
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	for (int i = 0; i < m; i++) {
		int u1, u2, u3;
		cin >> u1 >> u2 >> u3;
		e[u1].push_back(B{ u2,u3 });
		e[u2].push_back(B{ u1,u3 });
	}
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			for (int z = 0; z < 201; z++)
				a[i][j][z] = inf;
	priority_queue<P, vector<P>, greater<P>>p;
	p.push(P{ 1,0,0,0 });
	a[1][0][0] = 0;
	while (!p.empty()) {
		P t = p.top(); p.pop();
		for (int i = 0; i < e[t.pos].size(); i++) {
			if (b[e[t.pos][i].to] == 0) {
				if (t.deg == 0) {
					if (a[e[t.pos][i].to][0][0] > t.cost + e[t.pos][i].cost) {
						a[e[t.pos][i].to][0][0] = t.cost + e[t.pos][i].cost;
						p.push(P{ e[t.pos][i].to,t.cost + e[t.pos][i].cost,0,0 });
					}
				}
			if (t.deg == 2 && t.time+e[t.pos][i].cost >= x) {
					if (a[e[t.pos][i].to][0][0] > t.cost + e[t.pos][i].cost) {
						a[e[t.pos][i].to][0][0] = t.cost + e[t.pos][i].cost;
						p.push(P{ e[t.pos][i].to,t.cost + e[t.pos][i].cost ,0,0 });
					}
				}
			}
			else if (b[e[t.pos][i].to] == 1) {
				if (t.deg == 0) {
					if (a[e[t.pos][i].to][0][min(x, t.time + e[t.pos][i].cost)] > t.cost + e[t.pos][i].cost) {
						a[e[t.pos][i].to][0][min(x, t.time + e[t.pos][i].cost)] = t.cost + e[t.pos][i].cost;
						p.push(P{ e[t.pos][i].to,t.cost + e[t.pos][i].cost,0,min(x, t.time + e[t.pos][i].cost) });
					}
				}
				else if (t.deg == 2) {
					if (a[e[t.pos][i].to][2][min(x, t.time + e[t.pos][i].cost)] > t.cost + e[t.pos][i].cost) {
						a[e[t.pos][i].to][2][min(x, t.time + e[t.pos][i].cost)] = t.cost + e[t.pos][i].cost;
						p.push(P{ e[t.pos][i].to,t.cost + e[t.pos][i].cost,2,min(x,t.time + e[t.pos][i].cost) });
					}
				}
			}
			else {
				if (t.deg == 0 &&t.time+ e[t.pos][i].cost >= x) {
					if (a[e[t.pos][i].to][2][0] > t.cost + e[t.pos][i].cost) {
						a[e[t.pos][i].to][2][0] = t.cost + e[t.pos][i].cost;
						p.push(P{ e[t.pos][i].to,t.cost + e[t.pos][i].cost,2,0 });
					}
				}
				else if (t.deg == 2) {
					if (a[e[t.pos][i].to][2][0] > t.cost + e[t.pos][i].cost) {
						a[e[t.pos][i].to][2][0] = t.cost + e[t.pos][i].cost;
						p.push(P{ e[t.pos][i].to,t.cost + e[t.pos][i].cost,2,0 });
					}
				}
			}
		}
	}
	int ans = inf;
	for (int j = 0; j < 3; j++) {
		for (int i = 0; i < 201; i++)
			ans = min(ans, a[n][j][i]);
	}
	cout << ans << endl;
	getchar(); getchar();
}

Measured memory_bytes: 51840