import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.container;
import std.typecons;
import std.math;

void main(){
    alias Tuple!(int, int) edge;
    alias Tuple!(int, int, int, int) state; // dist, node, last temp, x

    int n, m, x;
    scanf("%d%d%d", &n, &m, &x);
    auto temp = new int[n];
    foreach(i; 0..n) scanf("%d", &temp[i]);
    auto graph = new edge[][](n);
    foreach(i; 0..m){
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        --a; --b;
        graph[a] ~= edge(b, d);
        graph[b] ~= edge(a, d);
    }

    auto dist = new int[][][](n, 3, 210); // node, last temp, x
    foreach(a; dist) foreach(b; a) b[] = int.max / 2;
    state[] a = [state(0,0,0,x)];
    auto q = new BinaryHeap!(Array!state, "a > b")();
    q.insert(state(0, 0, 0, x));
    int ans = -1;
    while(q.length != 0){
        int cd = q.front[0];
        int cn = q.front[1];
        int ct = q.front[2];
        int cx = q.front[3];
        q.removeFront;
        // writeln([cd, cn, ct, cx]);
        if(cn == n-1){
            ans = cd;
            break;
        }
        if(dist[cn][ct][cx] < cd) continue;

        foreach(const ref e; graph[cn]){
            int nd = cd + e[1];
            int nn = e[0];
            int nt = temp[nn] != 1 ? temp[nn] : ct;
            int nx = temp[nn] != 1 ? x : max(0, cx - e[1]);
            if(abs(nt - ct) == 2 && cx > e[1]) continue;
            if(dist[nn][nt][nx] > nd){
                dist[nn][nt][nx] = nd;
                q.insert(state(nd, nn, nt, nx));
            }
        }
    }
    writeln(ans);
}