先求出某一段时间[i,j]一直用同一个路径的最短路，乘上天数，记作cost[i,j]
那就可以设f[i]是前i天的最小代价，f[i]=f[j]+cost[j+1,i]+K
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=,maxm=; ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Edge{
int a,b,l,ne;
}eg[maxm*maxm*];
int N,M,K,E,D,egh[maxm],ect;
int di[maxm][maxn],dis[maxm],mi[maxm],cost[maxn][maxn];
int f[maxn];
bool can[maxm][maxn],used[maxm],flag[maxm]; inline void adeg(int a,int b,int l){
eg[++ect].a=a;eg[ect].b=b;eg[ect].l=l;eg[ect].ne=egh[a];egh[a]=ect;
} inline int dijkstra(){
priority_queue<pa,vector<pa>,greater<pa> > q;while(!q.empty()) q.pop();
memset(dis,,sizeof(dis));memset(flag,,sizeof(flag));
dis[]=;q.push(make_pair(,));
while(!q.empty()){
int p=q.top().second;q.pop();if(flag[p]||!used[p]) continue;
if(p==M) break;
for(int i=egh[p];i!=-;i=eg[i].ne){
int b=eg[i].b;
if(dis[b]>dis[p]+eg[i].l){
dis[b]=dis[p]+eg[i].l;
q.push(make_pair(dis[b],b));
}
}flag[p]=;
}return dis[M];
} inline void pre(){
for(int i=;i<=N;i++){
memset(mi,,sizeof(mi));
for(int j=i;j<=N;j++){memset(used,,sizeof(used));
used[]=used[M]=;
for(int k=;k<M;k++){
mi[k]=min(mi[k],(int)can[k][j]);
if(mi[k]) used[k]=;
}int re=dijkstra();
cost[i][j]=(re>=0x3f3f3f3f)?-:re*(j-i+);
//printf("%d %d %d\n",i,j,cost[i][j]);
}
}
} int main(){
int i,j,k;
N=rd(),M=rd(),K=rd(),E=rd();
memset(egh,-,sizeof(egh));
for(i=;i<=E;i++){
int a=rd(),b=rd(),c=rd();
adeg(a,b,c);adeg(b,a,c);
}D=rd();
for(i=;i<=D;i++){
int a=rd(),b=rd(),c=rd();
di[a][b]=;di[a][c+]=-;
}for(i=;i<=M;i++){
for(j=,k=;j<=N;j++){
k+=di[i][j];can[i][j]=k?:;
}
}pre();memset(f,,sizeof(f));f[]=-K;
for(i=;i<=N;i++){
for(j=;j<i;j++){
if(cost[j+][i]==-) continue;
f[i]=min(f[j]+cost[j+][i]+K,f[i]);
}//printf("%d %d\n",i,f[i]);
}printf("%d\n",f[N]);
return ;
}