#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 int long long
const int INF = 100100100100100LL;

using namespace std;

vector<int> dijk(int s, int v, const vector<vector<pair<int, int> > > &adjlist){

    priority_queue<pair<int, int> > wait;
    vector<int> result(v, INF);

    result[s] = 0;
    wait.push(make_pair(0, s));

    while(!wait.empty()){
        int nowpoint = wait.top().second;
        int nowcost = -wait.top().first;
        wait.pop();

        if(result[nowpoint] < nowcost) continue;

        for(int i = 0; i < adjlist[nowpoint].size(); i++){
            int nextpoint = adjlist[nowpoint][i].second;
            int nextcost = nowcost + adjlist[nowpoint][i].first;

            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push(make_pair(-nextcost, nextpoint));
            }
        }
    }

    return result;
}

signed main(){

    int n, m, x; cin >> n >> m >> x;
    vector<int> t(n);
    for(int i = 0; i < n; i++){
        cin >> t[i];
        if(t[i] == 1) t[i] = 0;
        else if(t[i] == 0) t[i] = 1;
        else t[i] = 2;
    }
    // toGraph[n][x][state]
    vector<vector<vector<int> > > toGraph(n, vector<vector<int> > (x + 1, vector<int> (3)));
    int num = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= x; j++){
            for(int k = 0; k < 3; k++){
                toGraph[i][j][k] = num;
                num++;   
            }
        }
    }

    vector<vector<pair<int, int> > > g(num);
    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        a--;
        b--;
        int cost = c;
        for(int z = 0; z < 2; z++){

            // a -> b
            int curNode = a;
            for(int curState = 0; curState < 3; curState++){
                // TODO 矛盾あるかも
                if(t[curNode] != 0 && curState != t[curNode]) continue;
                for(int curX = 0; curX <= x; curX++){
                    int nextNode = b;
                    int nextState;
                    int nextX;

                    if(curState == 0){
                        if(t[nextNode] == 0){
                            nextState = 0;
                            nextX = 0;
                        }else{
                            nextState = t[nextNode];
                            nextX = x;
                        }

                    }else{
                        if(t[curNode] != 0 && curX != x) continue;
                        if(t[nextNode] == 0){
                            nextState = curState;
                            nextX = max(0LL, curX - cost);
                            if(nextX == 0) nextState = 0;
                        }else if(t[nextNode] == curState){
                            nextState = curState;
                            nextX = x;
                        }else{
                            nextX = max(0LL, curX - cost);
                            if(nextX != 0) continue;
                            nextX = x;
                            nextState = t[nextNode];
                        }
                    }

                    int cur = toGraph[curNode][curX][curState];
                    int next = toGraph[nextNode][nextX][nextState];
          //          cerr << "(" << curNode + 1 << "," << curState << "," << curX << ")  --->>>   (" << nextNode + 1 << "," << nextState << "," << nextX << ")    :   " << cost << endl; 
                    g[cur].push_back({cost, next});
                }
            }

            swap(a, b);
        }
    }

    int S = toGraph[0][x][1];
    vector<int> result = dijk(S, num, g);
    /*
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= x; j++){
            for(int k = 0; k < 3; k++){
                int G = toGraph[i][j][k];
                cout << i + 1 << " " << k << " " << j << " " << result[G] << endl;
            }
        }
    }*/


    int ans = INF;
    for(int j = 0; j <= x; j++){
        for(int k = 0; k < 3; k++){
            int G = toGraph[n - 1][j][k];
            ans = min(ans, result[G]);
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 632080