#include<cstdio>
#include<algorithm>
#include<queue>
#include<ctype.h>
#include<cstring>
#define int long long

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f; 
 } 
 
int head[105],to[200005],nxt[200005],w[200005],cnt;

void add(int u,int v,int wi)
{
	++cnt;
	to[cnt]=v;
	nxt[cnt]=head[u];
	w[cnt]=wi;
	head[u]=cnt;
}

int dp[105],len[105][105],n,m,k,e;
bool cant[105][105],nowc[105];
int dis[105];

void spfa()
{
	memset(dis,0x7f7f7f7f,sizeof(dis));
	bool vis[105]={0};
	vis[1]=1;
	queue<int>Q;
	Q.push(1);
	dis[1]=0;
	while(!Q.empty())
	{
		int now=Q.front();
		Q.pop();
		vis[now]=0;
		for(int i=head[now];i;i=nxt[i])
		{
			int v=to[i];
			if(nowc[v])continue;
			if(dis[v]>dis[now]+w[i])
			{
				dis[v]=dis[now]+w[i];
				if(!vis[v])
				{
					vis[v]=1;
					Q.push(v);
				}
			}
		}
	}
}

signed main()
{
	n=read();m=read(),k=read();e=read();
	for(int i=1;i<=e;i++)
	{
		int u=read(),v=read(),wi=read();
		add(u,v,wi);add(v,u,wi);
	 } 
	int q=read();
	while(q--)
	{
		int p=read(),l=read(),r=read();
		for(;l<=r;l++)
			cant[l][p]=1; 
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			memset(nowc,false,sizeof(nowc));
			for(int l=i;l<=j;l++)
				for(int k=1;k<=m;k++)
					nowc[k]|=cant[l][k];
			spfa();
			len[i][j]=dis[m];
		}
	memset(dp,0x7f7f7f7f,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		dp[i]=len[1][i]*i;
		for(int j=1;j<i;j++)
		{
			dp[i]=min(dp[i],dp[j]+len[j+1][i]*(i-j)+k);
		}
	}
	printf("%lld",dp[n]);
	
	return 0;
}

为什么 spfa() 中的 dis 数组 memset(dis,0x7f7f7f7f,sizeof(dis)); 初始化会变成一个很大的数,甚至在最后计算dp数组会爆 longlong