/*
    Task        :
    Author      : Phumipat C. [MAGCARI]
    Language    : C++
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    // v is current node
    // p is current cost
    // oil is current oil
    // tic is current used ticket
    int v,p,oil,tic;
    bool operator < (const A&o) const{
        if(p != o.p)    return p>o.p;
        else            return oil<o.oil;
    }
};
priority_queue<A > heap;
struct B{
    // v is edge's destination
    // w is edge's weight
    int v,w;
};
vector<B > g[110];
int price[110],cost[110][110][2];
//Third dimension is amout of used ticket
int main(){
    int n,st,en,cap,m,u,v,w;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&price[i]);
    scanf("%d %d %d %d",&st,&en,&cap,&m);
    while(m--){
        scanf("%d %d %d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    //set default value of array to infinity except for the first node
    for(int i=1;i<=n;i++)
        for(int j=0;j<=cap;j++)
            cost[i][j][0] = cost[i][j][1] = 1e9;
    //start Dijkstra process
    cost[st][0][0] = 0;
    heap.push({st,0,0,0});
    while (!heap.empty()){
        A now = heap.top();
        heap.pop();
        if(now.v == en && now.oil == cap){
            printf("%d\n",now.p);
            break;
        }
        // use ticket
        if(now.tic == 0 && cost[now.v][cap][1] > now.p){
            cost[now.v][cap][1] = now.p;
            heap.push({now.v,now.p,cap,1});
        }
        //buy 1 unit of oil
        if(now.oil < cap && cost[now.v][now.oil+1][now.tic] > now.p + price[now.v]){
            cost[now.v][now.oil+1][now.tic] = now.p + price[now.v];
            heap.push({now.v,now.p + price[now.v],now.oil+1,now.tic});
        }
        //travel to nearby node
        for(auto x:g[now.v]){
            if(x.w <= now.oil && cost[x.v][now.oil-x.w][now.tic] > now.p){
                cost[x.v][now.oil-x.w][now.tic] = now.p;
                heap.push({x.v,now.p,now.oil-x.w});
            }
        }
    }
    // printf("%d\n",min(cost[en][cap][0],cost[en][cap][1]));
    return 0;
}