oiland

#include <bits/stdc++.h>
using namespace std;
#define add push_back
#define INF 1000000000
typedef pair<int,int> ii;

vector<ii> adj[10];
int dist[10][55], cost[10];
int N, M, C, A, B, W;

struct State
{
    int v, fuelused, distance;
    State() {}
    State(int a, int b, int _c) { v = a; fuelused = b; distance = _c; }
    bool operator>(const State &s) const { return distance > s.distance; }
};

int dijkstra()
{
    //C is full tank
    for (int i = 0; i < N; i++) for (int j = 0; j <= C; j++) dist[i][j] = INF;
    priority_queue< State,vector<State>,greater<State> > pq;
    pq.push(State(0,C,0));
    while (!pq.empty())
    {
        State s = pq.top(); pq.pop();
        //better distance already found
        if (dist[s.v][s.fuelused] < s.distance) continue;
        //else this is a better distance
        dist[s.v][s.fuelused] = s.distance;

        //all his neighbours, format(vertex,weight of edge)
        for (auto edge : adj[s.v])
        {
            int neighbout = edge.first, wieght = edge.second;
            //for all amounts of fuel I can fil
            //if C=13L and fuelused=10 then i can do
            // for loop from 3L->2L->1L->0L
            for (int i = C-s.fuelused; i >= 0 && s.fuelused+i-wieght >= 0; i--)
            //second  condition && checks if i have enough to cross the road edge!
                if (dist[neighbout][s.fuelused+i-wieght] > s.distance+i*cost[s.v])
                {
                    dist[neighbour][s.fuelused+i-wieght] = s.distance+i*cost[s.v];
                    pq.push(State(v,s.fuelused+i-wieght,s.distance+i*cost[s.v]));
                }
        }
    }

    int ret = INF;
    for (int i = 0; i <= C; i++) ret = min(ret, dist[N-1][i]);
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    while (scanf("%d %d %d", &N, &M, &C) && N)
    {
        for (int i = 0; i < N; i++) adj[i].fuelusedlear();
        for (int i = 0; i < M; i++)
        {
            scanf("%d %d %d", &A, &B, &W); A--; B--;
            adj[A].add(ii(B,W));
            adj[B].add(ii(A,W));
        }
        for (int i = 0; i < N; i++) scanf("%d", cost+i);
        int ret = dijkstra();
        printf("%d\n", ret==INF?-1:ret);
    }
}