#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
static const int dx[] = {0,0,1,-1};
static const int dy[] = {1,-1,0,0};
typedef pair< int,int > PII;
typedef pair< int,pair<int,int> > PPII;
typedef pair< int,pair<int,pair<int, int> > > PPPII;

struct edge{
    int to,cost;
    edge(){}
    edge(int p1,int p2){
        to=p1;
        cost=p2;
    }
};

typedef pair<int,int> PII;
vector<edge> G[10005];
int dist[10005][205][5];
int A[20005];
int N,M,X;


void dijkstra(int s){
    priority_queue<PPPII,vector<PPPII>,greater<PPPII> > que;
    for(int i=0;i<10005;++i)for(int j=0;j<=200;++j)for(int k=0;k<3;++k)dist[i][j][k]=INF;
    dist[s][0][A[s]]=0;
    que.push(PPPII(0,PPII(s,PII(0,A[s]))));
    while(!que.empty()){
        PPPII p = que.top();
        que.pop();
        int v=p.second.first;
        int time=p.second.second.first;
        int hot=p.second.second.second;
        if(dist[v][time][hot]<p.first)continue;
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            int ntime,nhot;
            if(A[e.to]==0){
                if(hot==2){
                    if(time+e.cost<X)continue;
                    else {
                        ntime=0;
                        nhot=A[e.to];
                        if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
                            dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
                            que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
                        }
                    }
                }
                if(hot==0){
                    ntime=0;
                    nhot=A[e.to];
                    if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
                        dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
                        que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
                    }
                }
            }
            else if(A[e.to]==2){
                if(hot==0){
                    if(time+e.cost<X)continue;
                    else {
                        ntime=0;
                        nhot=A[e.to];
                        if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
                            dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
                            que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
                        }
                    }
                }
                if(hot==2){
                    ntime=0;
                    nhot=A[e.to];
                    if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
                        dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
                        que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
                    }
                }
            }

            else if(A[e.to]==1){
                ntime=time+e.cost;
                nhot=hot;
                if(ntime>=X)ntime=200;
                if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){
                    dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost;
                    que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot))));
                }
            }
        }
    }
}

signed main(){
    cin>>N>>M>>X;
    for(int i=0;i<N;++i)cin>>A[i];
    for(int i=0;i<M;++i){
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        G[a].PB(edge(b,c));
        G[b].PB(edge(a,c));
    }
    dijkstra(0);
    int ans=INF;
    for(int i=0;i<=200;++i){
        for(int j=0;j<3;++j){
            ans=min(ans,dist[N-1][i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 84564