#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int maxn=110000;const int INF=0x3f3f3f3f;struct Edge{ int to,next,cost;}edge[maxn],edge2[maxn];int Adj[maxn/100],Adj2[maxn/100],Size,Size2;int fuel[maxn/100],price[maxn/100],n,m,c,p,q;void init(){ Size=Size2=0; memset(Adj,-1,sizeof(Adj)); memset(Adj2,-1,sizeof(Adj2)); memset(fuel,0,sizeof(fuel)); memset(price,0,sizeof(price));}void Add_Edge(int u,int v,int w){ edge[Size].next=Adj[u]; edge[Size].to=v; edge[Size].cost=w; Adj[u]=Size++;}void Add_Edge2(int u,int v,int w){ edge2[Size2].next=Adj2[u]; edge2[Size2].to=v; edge2[Size2].cost=w; Adj2[u]=Size2++;}int dmax[maxn/100],cq[maxn],dmin[maxn/100];bool inq[maxn/100];bool spfa_find_max(){ memset(dmax,-1,sizeof(dmax)); memset(cq,0,sizeof(cq)); memset(inq,false,sizeof(inq)); dmax[1]=c; queue<int> q; inq[1]=true,cq[1]=1; q.push(1); while(!q.empty()) { int u=q.front();q.pop(); for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(dmax[u]-edge[i].cost<0) continue; if(dmax[v]<dmax[u]-edge[i].cost) { if(fuel[v]) dmax[v]=c; else dmax[v]=dmax[u]-edge[i].cost; if(inq[v]==false) { inq[v]=true; cq[v]++; if(cq[v]>=n) return false; q.push(v); } } } inq[u]=false; } return true;}bool spfa_find_min(){ memset(dmin,63,sizeof(dmin)); memset(inq,false,sizeof(inq)); memset(cq,0,sizeof(cq)); dmin[n]=0; queue<int> q; q.push(n); inq[n]=true,cq[n]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=Adj2[u];~i;i=edge2[i].next) { int v=edge2[i].to; if(dmin[u]+edge2[i].cost>c) continue; if(dmin[v]>dmin[u]+edge2[i].cost) { if(fuel[v]) dmin[v]=0; else { dmin[v]=dmin[u]+edge2[i].cost; } if(inq[v]==false) { inq[v]=true; cq[v]++; if(cq[v]>=n) return false; q.push(v); } } } inq[u]=false; } return true;}int main(){ while(scanf("%d%d%d",&n,&m,&c)!=EOF) { init(); for(int i=0;i<m;i++) { int u,v,x; scanf("%d%d%d",&u,&v,&x); Add_Edge(u,v,x); Add_Edge2(v,u,x); } scanf("%d",&p); for(int i=0;i<p;i++) { int x; scanf("%d",&x); fuel[x]=1; } scanf("%d",&q); for(int i=0;i<q;i++) { int x,y; scanf("%d%d",&x,&y); price[x]=y; } spfa_find_max(); spfa_find_min(); if(dmax[n]==-1||dmin[1]==INF) puts("-1"); else { int ans=0; for(int i=1;i<=n;i++) { if(price[i]&&dmax[i]!=-1&&dmin[i]!=INF) { ans=max(ans,price[i]*(dmax[i]-dmin[i])); } } printf("%dn",ans); } } return 0;}
