/* ***********************************************Author        :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dec(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=2e3+10;int n,m,k,e,x,y,t;int id[N],ax[N],ay[N],dp[105],d[21];bool vis[21];vector<pair<int,int> >eg[21];struct node{    int v,d;    node(int a=0,int b=0):v(a),d(b){}    bool operator < (const node &a) const    {        return d>a.d;    }};void dijkstra(int d1,int d2){    memset(vis,0,sizeof(vis));    memset(d,inf,sizeof(d));    d[1]=0;    rep(i,1,e) if(!(ax[i]>d2||ay[i]<d1)) vis[id[i]]=1;    priority_queue<node>q;    q.push(node(1,0));    node tmp;    while(!q.empty())    {        tmp=q.top();        q.pop();        int u=tmp.v;        if(vis[u]) continue;        vis[u]=1;        rep(i,0,eg[u].size()-1)        {            int v=eg[u][i].first,w=eg[u][i].second;            if(!vis[v]&&d[v]>d[u]+w)            {                d[v]=d[u]+w;                q.push(node(v,d[v]));            }        }    }}int main(){    rd(n),rd(m),rd(k),rd(e);    while(e--)    {        rd(x),rd(y),rd(t);        eg[x].pb(mkp(y,t));        eg[y].pb(mkp(x,t));    }    rd(e);    rep(i,1,e) rd(id[i]),rd(ax[i]),rd(ay[i]);    rep(i,1,n)    {        dp[i]=inf;        rep(j,1,i)        {            dijkstra(j,i);            if(d[m]!=inf) dp[i]=min(dp[i],dp[j-1]+(i-j+1)*d[m]+k);        }    }    ou(dp[n]-k);    return 0;}