#include <bits/stdc++.h>

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937_64 rnd64(std::chrono::steady_clock::now().time_since_epoch().count());

const int N=101;
const ll INF=1ll<<59;

struct Node
{
    int first,second,third;
    ll fourth;
    bool operator < (const Node& A) const 
    {
        return fourth>A.fourth;
    }
    bool operator > (const Node& A) const 
    {
        return fourth<A.fourth;
    }
};

struct Edge
{
    int first;ll second,third;
};

int n,m,K,G;
ll dis[N][N][N];
bool vis[N][N][N];
vector<Edge> linker[N];
priority_queue<Node> qu;

void update(int u,int s,int t,ll w)
{
    if(dis[u][s][t]>w)
    {
        dis[u][s][t]=w;
        qu.push({u,s,t,w});
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m>>K>>G;
    vector<ll> x(n+1),y(n+1),z(n+1);
    rep(i,1,n) cin>>x[i]>>y[i]>>z[i];
    rep(i,1,m)
    {
        int u,v;ll p,q;
        cin>>u>>v>>p>>q;
        linker[u].push_back({v,p,q});
        linker[v].push_back({u,p,q});
    }
    rep(i,1,n) rep(j,0,K) rep(k,0,G) dis[i][j][k]=INF;
    dis[1][0][0]=0;
    qu.push({1,0,0,0ll});
    while(!qu.empty())
    {
        int u=qu.top().first,s=qu.top().second,t=qu.top().third;
        ll l=qu.top().fourth%(x[u]+y[u]+z[u]),d=qu.top().fourth,r=x[u]+y[u]+z[u];
        qu.pop();
        if(u==n)
        {
            cout<<d<<endl;
            return 0;
        }
        if(vis[u][s][t]) continue;
        vis[u][s][t]=1;
        for(auto i:linker[u])
        {
            int v=i.first,p=i.second,q=i.third;
            // 按红绿灯讨论
            if(l<x[u])
            {
                /*不限速*/ update(v,s,t,d+p);
                /*限速*/ if(s<K) update(v,s+1,t,d+q);
            }
            else if(l<(x[u]+y[u]))
            {
                // 不闯黄灯
                    /*不限速*/ update(v,s,t,d+r-l+p);
                    /*限速*/ if(s<K) update(v,s+1,t,d+r-l+q);
                // 闯黄灯
                if(t<G)
                {
                    update(v,s,t+1,d+p);
                    if(s<K) update(v,s+1,t+1,d+q);
                }
            }
            else
            {
                update(v,s,t,d+r-l+p);
                if(s<K) update(v,s+1,t,d+r-l+q);
            }
        }
    }
    return 0;
}

真服了，大佬们帮我解决 ub 以后，$\text{\color{red}{WA}}\times 9$。

数据非常非常非常非常水，我两个样例都没过过了一堆数据，应该说是大部分。

瞪了好长时间，都要玉玉了，求助。