#include<bits/stdc++.h> #define int long long using namespace std; bool chxulong[1000]; int markchxulong[1000][1000],SUM[1000][1000],f[1000],K,E; struct edge { int to,dis,next; }; edge e[50001]; int head[10001],dis[10001],cnt,n,m,s; bool vis[10001]; void add_edge(int u,int v,int d) { cnt++; e[cnt].dis=d; e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } struct node{ int dis; int pos; bool operator <(const node &x)const { return x.dis<dis; } }; priority_queue<node> q; void dijkstra() { for(int i=1;i<=m;i++){ dis[i]=0x3f3f3f3f; vis[i]=0; } dis[s]=0; while(q.size()) q.pop(); q.push((node){0,s}); while(!q.empty()){ node tmp=q.top(); q.pop(); int x=tmp.pos,d=tmp.dis; if(vis[x])continue; vis[x]=true; for(int i=head[x];i;i=e[i].next){ int y=e[i].to; if(chxulong[y])continue; if(dis[y]>dis[x]+e[i].dis){ dis[y]=dis[x]+e[i].dis; if(!vis[y]) q.push((node){dis[y],y}); } } } } signed main() { s=1; cin>>n>>m>>K>>E; for(int i=0;i<10001;i++) dis[i]=INT_MAX; while(E--){ int u,v,d; cin>>u>>v>>d; add_edge(u,v,d); add_edge(v,u,d); } int q; cin>>q; int P,A,B; while(q--){ cin>>P>>A>>B; for(int i=A;i<=B;i++) markchxulong[P][i]=true; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ memset(chxulong,0,sizeof(chxulong)); cnt=0; for(int k=1;k<=m;k++){ for(int o=i;o<=j;o++){ if(markchxulong[k][o]) chxulong[k]=true; } } dijkstra(); SUM[i][j]=dis[m]; } } memset(f,0x3f3f3f3f,sizeof(f)); for(int i=1;i<=n;i++){ f[i]=i*SUM[1][i]; for(int j=1;j<i;j++) f[i]=min(f[i],f[j]+((i-j)*SUM[j+1][i]+K)); } cout<<f[n]; return 0; }