#include<bits/stdc++.h> using namespace std; bool chxulong[1000]; int markchxulong[1000][1000],SUM[1000][1000],P,A,B,f[1000],K,E,head[10001],dis[10001],cnt,n,m,s=1; struct edge{ int to,dis,next; }; edge e[50001]; 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,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}); } } } } int main(){ 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; 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; }