预处理出ans[i][j]为i到j时间的最短路，设f[i]为到i时间的最小代价，转移显然就是 f[i]=min(f[j-1]+ans[j][i]*(i-j+1)+k);
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=25;
long long n,m,k,e,a[N][N],d,ans[105][105],f[105]={0};
bool b[N][105];
long long dfs(long long s,long long t)
{
queue<long long>q;
long long dis[21]={0};
bool lock[21]={0};
for(long long i=1;i<=m;i++)
for(long long j=s;j<=t;j++)
if(b[i][j]==0)
{
lock[i]=1;
break;
}
for(long long i=1;i<=m;i++)
dis[i]=1e9;
dis[1]=0;
q.push(1);
while(!q.empty())
{
long long u=q.front();
q.pop();
for(long long i=1;i<=m;i++)
if(a[i][u]&&!lock[i]&&dis[i]>a[i][u]+dis[u])
{
dis[i]=a[i][u]+dis[u];
q.push(i);
}
}
return dis[m];
}
int main()
{
memset(b,1,sizeof(b));
scanf("%lld%lld%lld%lld",&n,&m,&k,&e);
for(long long i=1,x,y,z;i<=e;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
a[x][y]=a[y][x]=z;
}
scanf("%lld",&d);
for(long long i=1,x,y,z;i<=d;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
for(long long j=y;j<=z;j++)
b[x][j]=0;
}
for(long long i=1;i<=n;i++)
for(long long j=1;j<=n;j++)
ans[i][j]=dfs(i,j);
for(long long i=1;i<=n;i++)
f[i]=1e9;
f[0]=-k;
for(long long i=1;i<=n;i++)
for(long long j=1;j<=i;j++)
f[i]=min(f[i],f[j-1]+ans[j][i]*(i-j+1)+k);
printf("%lld
",f[n]);
return 0;
}