#include<iostream>
#include<queue>
#include<algorithm>
#include<functional>
#include<vector>

using namespace std;
typedef pair<int, pair<int, pair<int, int>>> P;

struct Edge {
	int to, cost;
	Edge() = default;
	Edge(int t, int c) {
		to = t, cost = c;
	}
};

int temp[10000];

int N, M, X;
vector<vector<Edge>> edge;

int d[10000][3][200 + 1];

int djk(int s, int e) {
	for (int i = 0; i < N; i++)for (int j = 0; j < 3; j++)for (int k = 0; k <= X; k++)d[i][j][k] = 100000007;
	d[s][0][X] = 0;
	priority_queue < P, vector<P>, greater<P>> pq;
	pq.push(P(0, make_pair(s, make_pair(0, X))));
	while (pq.size()) {
		auto tmp = pq.top(); pq.pop();
		if (tmp.first > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second])continue;
		//cout << tmp.first << " " << tmp.second.first << " " << tmp.second.second.first << " " << tmp.second.second.second << endl;

		for (int i = 0; i < edge[tmp.second.first].size(); i++) {
			auto& tonext = edge[tmp.second.first][i];

			//cout << i << "A" << edge[tmp.second.first][i].to << " " << edge[tmp.second.first][i].cost << endl;

			if (tmp.second.second.first == 0) {
				if (temp[tonext.to] == 2) {
					if (tmp.second.second.second - tonext.cost <= 0) {
						//????????±
						if (d[tonext.to][2][X] > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost) {
							d[tonext.to][2][X] = d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost;
							pq.push(P(d[tonext.to][2][X], make_pair(tonext.to, make_pair(2, X))));
						}
					}
				}
				else if (temp[tonext.to] == 0) {
					//?????????
					if (d[tonext.to][0][X] > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost) {
						d[tonext.to][0][X] = d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost;
						pq.push(P(d[tonext.to][0][X], make_pair(tonext.to, make_pair(0, X))));
					}
				}
				else {
					//????????????
					if (d[tonext.to][0][max(tmp.second.second.second - tonext.cost, 0)] > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost) {
						d[tonext.to][0][max(tmp.second.second.second - tonext.cost, 0)] = d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost;
						pq.push(P(d[tonext.to][0][max(tmp.second.second.second - tonext.cost, 0)],
							make_pair(tonext.to, make_pair(0, max(tmp.second.second.second - tonext.cost, 0)))));
					}
					//cout << d[tonext.to][0][max(tmp.second.second.second - tonext.cost, 0)] << " " << tonext.to << " 1 " << max(tmp.second.second.second - tonext.cost, 0) << endl;
				}
			}
			else if (tmp.second.second.first == 2) {
				if (temp[tonext.to] == 0) {
					if (tmp.second.second.second - tonext.cost <= 0) {
						//??±??????
						if (d[tonext.to][0][X] > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost) {
							d[tonext.to][0][X] = d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost;
							pq.push(P(d[tonext.to][0][X], make_pair(tonext.to, make_pair(0, X))));
						}
					}
				}
				else if (temp[tonext.to] == 2) {
					//??±?????±
					if (d[tonext.to][2][X] > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost) {
						d[tonext.to][2][X] = d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost;
						pq.push(P(d[tonext.to][2][X], make_pair(tonext.to, make_pair(2, X))));
					}
				}
				else {
					//??±?????????
					if (d[tonext.to][2][max(tmp.second.second.second - tonext.cost, 0)] > d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost) {
						d[tonext.to][2][max(tmp.second.second.second - tonext.cost, 0)] = d[tmp.second.first][tmp.second.second.first][tmp.second.second.second] + tonext.cost;
						pq.push(P(d[tonext.to][2][max(tmp.second.second.second - tonext.cost, 0)],
							make_pair(tonext.to, make_pair(2, max(tmp.second.second.second - tonext.cost, 0)))));
					}
				}
			}
		}

	}

	int ans = 1000000007;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j <= X; j++) {
			ans = min(ans, d[e][i][j]);
		}
	}
	return ans;
}

int main() {
	cin >> N >> M >> X;
	for (int i = 0; i < N; i++) {
		cin >> temp[i];
	}
	edge.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c; a--, b--;
		edge[a].push_back(Edge(b, c));
		edge[b].push_back(Edge(a, c));
	}
	cout << djk(0, N - 1) << endl;
	return 0;
}

Measured memory_bytes: 27492