#include<bits/stdc++.h>

using namespace std;

long long A,B,C,z,y,x;

long long f[1010];                                                           //f[i]表示1->i的最小花费

long long n,m,k,e;

long long dis[1001][1001],D,d[1001][1001];

bool flg[1001],b[1001][1001];

inline int read(){

    int ret=0,f=1,ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}

    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();

    return ret*f;

}

inline void write(int x){

    if(x/10)write(x/10);putchar(x%10+'0');

}

int main(){

    n=read(),m=read(),k=read(),e=read();

    for(int i=1;i<=m;i++)                                                    //初始化

    for(int j=1;j<=m;j++)

    dis[i][j]=21474836;

    for(int i=1;i<=e;i++)

    A=read(),B=read(),C=read(),dis[B][A]=dis[A][B]=C;D=read();               //建边

    for(int i=1;i<=D;i++){                                                   //b[i][j]表示i港口（航线）b时间内无法通行

        z=read(),x=read(),y=read();

        for(int j=x;j<=y;j++)b[z][j]=1;

    }

    memset(f,60,sizeof(f));

    f[0]=-k;                                                                 //为了抵消下面的“＋k”

    for(int i=1;i<=n;i++){

        memset(flg,0,sizeof(flg));

        for(int j=i;j>=1;j--){                                               //逆枚！

            for(int kk=1;kk<=m;kk++)flg[kk]+=b[kk][j];                       //判断i->j区间内可否通行（有1个时刻不能通行就绝对不能通行）

            for(int kk=1;kk<=m;kk++)                                         //Copy

            for(int l=1;l<=m;l++)

            {

                if(!flg[kk]&&!flg[l])d[kk][l]=dis[kk][l];

                else d[kk][l]=21474836;

            }

            for(int kk=1;kk<=m;kk++)                                         //Floyd

            for(int ii=1;ii<=m;ii++)

            for(int jj=1;jj<=m;jj++)

            if(!flg[ii]&&!flg[jj]&&!flg[kk])

            d[ii][jj]=min(d[ii][jj],d[ii][kk]+d[kk][jj]);

            if(d[1][m]==21474836)continue;                                   //不满足可到达终点原则

            f[i]=min(f[i],f[j-1]+k+d[1][m]*(i-j+1));                         //1->j-1用一种方案，j->i用另一种方案。为保证j->i方案可行性，j必须从i->1枚举

        }

    }

    printf("%d",f[n]);

}