#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <stdint.h>
 
#define in std::cin
#define out std::cout
 
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <algorithm>
#include <iterator>
 
using COST_T = int32_t;
constexpr uint32_t N_MAX = 10000;
constexpr COST_T INF = 10000 * 400 + 1000;//std::numeric_limits<double>::infinity()
 
#if defined(_MSC_VER) && defined(_DEBUG)
                                          //static_assert(false, "???????????????§???????????????????????????¨???????????????");
#endif
 
struct edge {
    uint32_t to;
    COST_T cost;
    edge() {}
    edge(uint32_t to_, COST_T cost_)
        :to(to_), cost(cost_) {}
};
std::vector<edge> graph[N_MAX];
 
int32_t N, M, X;
int32_t T[N_MAX];
 
//??????????????????
COST_T D[N_MAX][201][2];
void Dijkstra(uint32_t s)
{
    using P = std::pair<COST_T, uint64_t>;//cost pos
    std::priority_queue<P, std::vector<P>, std::greater<>> que;
    for(auto&arr2:D)for (auto&arr1 : arr2)for (auto&i : arr1)i=INF;
 
    D[s][X][0] = 0;
    que.emplace(0, ((uint64_t)(s)<<16)|(X<<8));
    while (!que.empty())
    {
        auto p = que.top(); que.pop();
        const auto nowpos = p.second >> 16;
        int32_t ntime = (p.second >> 8) & 0b1111'1111;
        int32_t ishot = p.second & 0b1111'1111;
        const auto& nowcost = p.first;
 
        if (D[nowpos][ntime][ishot] < nowcost) { continue; }
        //printf("%d,%d,%d,%d\n", nowpos, ntime, ishot, D[nowpos][ntime][ishot]);
        //for (int32_t to = 0; to < N; ++to)
        //{
        //  auto cost = nowcost + graph[nowpos][to];
        //  if (cost < D[to]) {
        //      D[to] = cost;
        //      que.emplace(D[to], to);
        //  }
        //}
 
        for (const auto& e : graph[nowpos])
        {
            auto cost = nowcost + e.cost;
            auto time = std::max<int32_t>(0, ntime - e.cost);
            if (time <= 0 || !((T[e.to] == 2 && !ishot) || (T[e.to] == 0 && ishot))) {
                auto nextishot = ishot;
                if (T[e.to] == 2) {
                    time = X;
                    nextishot = 1;
                }
                else if (T[e.to] == 0) {
                    time = X;
                    nextishot = 0;
                }
                else if (ntime <= 0) {
                    nextishot = 0;
                }
                if (cost < D[e.to][time][nextishot]) {
                    D[e.to][time][nextishot] = cost;
                    que.emplace(cost, ((int64_t)(e.to) << 16) | (time << 8) | nextishot);
                }
            }
        }
 
    }
}
 
#if 0
uint32_t DP[10000][201][2];
//???´????????????§??????¨??????????????????
uint32_t func(int pos, int wait, int type/*0??????,1???±???*/)
{
    if (pos == N - 1) { return 0; }
    if (T[pos] != 1) {
        //?\??????????¨??±?
        wait = X;
        if (T[pos] == 0) {
            type = 0;
        }
        else {
            type = 1;
        }
    }
    else if (wait == 0) {
        type = 0;
    }
 
    if (DP[pos][wait][type] != 0) { return DP[pos][wait][type]; }
    DP[pos][wait][type] = INF;
    uint32_t mincost = INF;
    for (const auto& e : graph[pos])
    {
        if (e.cost < wait) {
            //???°??¢?????????????§??????
            if (T[e.to] == 0 && type == 1) {
                continue;
            }
            if (T[e.to] == 2 && type == 0) {
                continue;
            }
        }
        mincost = std::min(mincost, func(e.to, std::max(0, wait - e.cost), type) + e.cost);
    }
    return DP[pos][wait][type] = mincost;
}
#endif
int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
 
    in >> N >> M >> X;
    for (size_t i = 0; i < N; ++i) {
        in >> T[i];
    }
    for (size_t i = 0; i < M; ++i) {
        int a, b, j;
        in >> a >> b >> j; --a; --b;
        graph[a].emplace_back(b, j);
        graph[b].emplace_back(a, j);
    }
    Dijkstra(0);
    int32_t res = INF;
    for (size_t i = 0; i <= X; ++i)
    {
        res = std::min(res, D[N - 1][i][0]);
        res = std::min(res, D[N - 1][i][1]);
    }
    out << res << endl;
 
    return 0;
}
#endif

Measured memory_bytes: 19924