#include<bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
int n,m,k,g,limits[25],belong[25],cur,sum[(1<<25)+50],pbelong[(1<<25)+50],f[2][200005][25],head[200005<<1],tot;
vector<int> p[25];
struct edge{
	int u,v,w;
	int next;
}e[200005<<1];
void add(int u,int v,int w){
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].next=head[u];
	head[u]=tot;
}
int dis[20005],dist[25][2],diss[25][25];
bool vis[20005];
void dijkstra(int x){
	memset(dis,0x3f3f3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[belong[x]]=0;
	priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >Q;
	while(!Q.empty())
		Q.pop();
	Q.push({0,belong[x]});
	while(!Q.empty()){
		pair<int,int>  s=Q.top();
		Q.pop();
		int temp=s.second,distance=s.first;
		if(vis[temp]==1) continue;
		vis[temp]=1;
		for(int i=head[temp];i;i=e[i].next){
			int j=e[i].v;
			if(distance+e[i].w<dis[j]){
				dis[j]=distance+e[i].w;
				Q.push({dis[j],j});
			}
		}
	}
	dist[x][0]=dis[1],dist[x][1]=dis[n];
	for(int i=0;i<k;++i)
		diss[x][i]=dis[belong[i]];
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	if(k!=0){							
		scanf("%d",&g);
		int r,s;
		for(int i=1;i<=g;i++){
			scanf("%d%d",&r,&s);
			limits[s-2]|=(1<<(r-2));
		}
	}
	if(k==0){
		belong[1]=1;		
		dijkstra(1);
		printf("%d\n",dis[n]);
		return 0;
	}
	for(int i=0;i<k;i++)
		belong[i]=i+2;
	for(int s=1;s<(1<<k);s++){
		sum[s]=sum[s&(~(lowbit(s)))]+1;
		p[sum[s]].push_back(s);
		pbelong[s]=p[sum[s]].size()-1;
	}
	memset(f,0x3f,sizeof(f));
	for(int i=0;i<k;i++){
		dijkstra(i);
		if(!limits[i])	
			f[cur][pbelong[1<<i]][i]=dist[i][0];
	}
	cur=0;
	for(int i=2;i<=k;i++){
		int len=p[i].size();
		cur^=1;			
		memset(f[cur],0x3f,sizeof(f[cur]));
		for(int e=0;e<len;e++){
			int s=p[i][e];
			for(int j=0;j<k;j++)
				if((s&(1<<j))&&((limits[j]&(s&(~(1<<j))))==limits[j]))
					for(int q=0;q<k;++q)
						if(j!=q&&(s&(1<<q)) )
							f[cur][e][j]=min(f[cur][e][j],f[cur^1][pbelong[s&(~(1<<j))]][q]+diss[q][j]);
		}
	}
	int ans=0x3f3f3f;
	for(int i=0;i<k;i++)
		ans=min(ans,f[cur][0][i]+dist[i][1]);
	printf("%d\n",ans);
	return 0;
}