#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a) = min((a), (b)))
#define chmax(a, b) ((a) = max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1);
const double eps = 1e-10;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

vector<vector<P>> G(10010);
vector<int> t(10010);

int n, m, x;

int dijkstra(int s){
    int dist[n][x+1][3];
    for(int i=0; i<n; i++){
        for(int j=0; j<=x; j++){
            for(int k=0; k<3; k++){
                dist[i][j][k] = 1e9;
            }
        }
    }

    priority_queue<T, vector<T>, greater<T>> que;
    dist[s][x][0] = 0;
    que.emplace(0, s, x, 0);

    while(!que.empty()){
        int ccost, cv, cx, ct;
        tie(ccost, cv, cx, ct) = que.top();
        que.pop();

        if(dist[cv][cx][ct] < ccost) continue;

        for(auto X : G[cv]){
            int nv, ncost;
            tie(nv, ncost) = X;

            int restx = max(0, cx - ncost);

            if(restx == 0){
                if(t[nv] == 0){
                    if(dist[cv][cx][ct] + ncost < dist[nv][x][0]){
                        dist[nv][x][0] = dist[cv][cx][ct] + ncost;
                        que.emplace(dist[nv][x][0], nv, x, 0);
                    }
                }
                else if(t[nv] == 1){
                    if(dist[cv][cx][ct] + ncost < dist[nv][0][1]){
                        dist[nv][0][1] = dist[cv][cx][ct] + ncost;
                        que.emplace(dist[nv][0][1], nv, 0, 1);
                    }
                }
                else{
                    if(dist[cv][cx][ct] + ncost < dist[nv][x][2]){
                        dist[nv][x][2] = dist[cv][cx][ct] + ncost;
                        que.emplace(dist[nv][x][2], nv, x, 2);
                    }
                }
            }
            else{
                if(t[nv] == 0){
                    if(ct == 2) continue;

                    if(dist[cv][cx][ct] + ncost < dist[nv][x][0]){
                        dist[nv][x][0] = dist[cv][cx][ct] + ncost;
                        que.emplace(dist[nv][x][0], nv, x, 0);
                    }
                }
                else if(t[nv] == 1){
                    if(dist[cv][cx][ct] + ncost < dist[nv][restx][ct]){
                        dist[nv][restx][ct] = dist[cv][cx][ct] + ncost;
                        que.emplace(dist[nv][restx][ct], nv, restx, ct);
                    }
                }
                else{
                    if(ct == 0) continue;

                    if(dist[cv][cx][ct] + ncost < dist[nv][x][2]){
                        dist[nv][x][2] = dist[cv][cx][ct] + ncost;
                        que.emplace(dist[nv][x][2], nv, x, 2);
                    }
                }
            }   
        }
    }

    int ans = 1e9;
    for(int i=0; i<=x; i++){
        for(int j=0; j<3; j++){
            ans = min(ans, dist[n-1][i][j]);
        }
    }

    return ans;
}

int main(){
    cin>>n>>m>>x;
    for(int i=0; i<n; i++) cin>>t[i];

    for(int i=0; i<m; i++){
        int a, b, d; cin>>a>>b>>d;
        a--, b--;
        G[a].emplace_back(b, d);
        G[b].emplace_back(a, d);
    }

    cout << dijkstra(0) << endl;
}


Measured memory_bytes: 27376