o57_oct_c2_kshort

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli INF = 1e18;
const int maxN = 1e4 + 10;
const int maxS = 50 + 10;
using pl = pair <lli, lli>;
using pll = pair <lli, pl>;
vector <pl> ng[maxN], sg[maxN];
bool vs[maxN][maxS];
lli dis[maxN][maxS];
lli N, M, S, L;

int main(){

    scanf("%lld %lld %lld %lld", &N, &M, &S, &L);

    for(int i=1;i<=M;i++){
        lli u, v, w;
        scanf("%lld %lld %lld", &u, &v, &w);
        ng[u].push_back({v, w});
    }

    for(int i=1;i<=S;i++){
        lli u, v, w;
        scanf("%lld %lld %lld", &u, &v, &w);
        sg[u].push_back({v, w});
    }

    priority_queue <pll, vector <pll>, greater <pll>> pq;
    dis[1][0] = 0;
    pq.push({ dis[1][0] , {1, 0} });

    for(int u=0;u<=N;u++){
        for(int l=0;l<=L;l++){
            dis[u][l] = INF;
        }
    }

    while(!pq.empty()){
        lli d = pq.top().first;
        lli u = pq.top().second.first;
        lli l = pq.top().second.second;
        pq.pop();
        if(vs[u][l]) continue;
        vs[u][l] = true;
        if(u == N){
            printf("%lld", d);
            return 0;
        }
        for(auto vw: ng[u]){
            lli v = vw.first;
            lli w = vw.second;
            if(!vs[v][l] and d + w < dis[v][l]){
                dis[v][l] = d + w;
                pq.push({dis[v][l], {v, l}});
            }
        }
        if(l < S){
            for(auto vw: sg[u]){
                lli v = vw.first;
                lli w = vw.second;
                if(!vs[v][l + 1] and d + w < dis[v][l + 1]){
                    dis[v][l + 1] = d + w;
                    pq.push({dis[v][l + 1], {v, l + 1}});
                }
            }
        }
    }

    return 0;
}