#include <bits/stdc++.h>
using namespace std;
const int MAXN=110,MAXM=220;
int n,m,k,g;
int red[MAXN],yellow[MAXN],green[MAXN],dis[MAXN][MAXN][MAXN];
struct edge
{
    int v,p,q;
};
vector <edge> e[MAXN] ;
struct node
{
    int u,xs,chd,dis;
    bool operator <(const node a)const
    {
        return dis>a.dis;
    }
};
priority_queue <node> q;
void update(int nod,int xs,int chd,int w)
{
    if(dis[nod][xs][chd]>w)
        dis[nod][xs][chd]=w,
        q.push({nod,xs,chd,w});
}
void dijkstra()
{
    //dis[v][xs][chd]
    memset(dis,0x3f,sizeof(dis));
    dis[1][0][0]=0;
    q.push({1,0,0,0});
    while(!q.empty())
    {
        node front=q.top();
        q.pop();
        int u=front.u,xs=front.xs,chd=front.chd;
        int nowdis=front.dis,nowlight=nowdis%(green[u]+yellow[u]+red[u]);
        if(dis[u][xs][chd]!=nowdis)continue;
        for(int i=0;i<e[u].size();i++)
        {
            int v=e[u][i].v,p_tim=e[u][i].p,q_tim=e[u][i].q;
            if(xs<k)
            {
                if(nowlight<green[u])
                    update(v,xs+1,chd,nowdis+p_tim);
                else
                    update(v,xs+1,chd,nowdis+green[u]+yellow[u]+red[u]-nowlight+p_tim);
                if(chd<g)
                    if(nowlight<green[u]+yellow[u])
                        update(v,xs+1,chd+1,nowdis+p_tim);
                    else update(v,xs+1,chd+1,nowdis+green[u]+red[u]+yellow[u]-nowlight+p_tim);
            }
            if(nowlight<green[u])
                update(v,xs,chd,nowdis+q_tim);
            else update(v,xs,chd,nowdis+green[u]+yellow[u]+red[u]-nowlight+q_tim);
            if(chd<g)
            {
                if(nowlight<green[u]+yellow[u])
                    update(v,xs,chd+1,nowdis+q_tim);
                else update(v,xs,chd+1,nowdis+green[u]+yellow[u]+red[u]-nowlight+q_tim);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k>>g;
    k=m-k;
    for(int i=1;i<=n;i++)
        cin>>green[i]>>yellow[i]>>red[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,p,q;
        cin>>u>>v>>p>>q;
        e[u].push_back({v,p,q});
        e[v].push_back({u,p,q});
    }
    dijkstra();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++)
        for(int j=0;j<=g;j++)
            ans=min(ans,dis[n][i][j]);
    if(ans==0x3f3f3f3f)cout<<-1;
    else cout<<ans;
    return 0;
}