#include <bits/stdc++.h> #define int long long using namespace std; bool lock[100]; int marklock[100][100]; int SUM[10000][10000]; int f[10000]; int K,E; struct edge { int to,dis,next; }; edge e[500010]; int head[100010],dis[100010],cnt; bool vis[100010]; int n,m,s; 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(lock[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->startspot s=1; cin >> n >> m >> K >> E; for(int i = 0; i < 100010; 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++) { marklock[P][i]=true; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { memset(lock,0,sizeof(lock)); cnt=0; for(int k = 1; k <= m; k++) { for(int o = i; o <= j; o++) { if(marklock[k][o]) { lock[k]=true; } } } dijkstra(); //cout << dis[m] << " "; SUM[i][j]=dis[m]; } } /* cout << endl; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cout << SUM[i][j] << " "; } cout << endl; } */ 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] << endl; return 0; }