#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <iostream>

using namespace std;

#define N 20005

#define M 1<<20

struct node

{

	int to,next,val;

}e[N*20];

int head[N],cnt,f[(M)+10][21],map[21][21],dis[N],vis[N],g[N],cur[21],n,m,k;

priority_queue <pair<int ,int > >q;

void add(int x,int y,int z)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	e[cnt].val=z;

	head[x]=cnt++;

}

void Dijkstra(int S)

{

	memset(dis,0x3f,sizeof(dis));

	memset(vis,0,sizeof(vis));

	while(!q.empty())q.pop();

	q.push(make_pair(0,S));dis[S]=0;

	int num=0;

	while(!q.empty())

	{

		if(num==n)break;

		int x=q.top().second;q.pop();

		if(vis[x])continue;

		vis[x]=1;

		num++;

		for(int i=head[x];i!=-1;i=e[i].next)

		{

			int to1=e[i].to;

			if(dis[to1]>dis[x]+e[i].val)

			{

				dis[to1]=dis[x]+e[i].val;

				q.push(make_pair(-dis[to1],to1));

			}

		}

	}

	for(int i=1;i<=k;i++)map[S-1][i]=dis[i+1];

	if(!cur[S-1])f[1<<(S-2)][S-1]=dis[1];

	g[S-1]=dis[n];

}

int main()

{

	memset(head,-1,sizeof(head));

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=m;i++)

	{

		int x,y,z;

		scanf("%d%d%d",&x,&y,&z);

		add(x,y,z);add(y,x,z);

	}

	if(!k)

	{

		Dijkstra(1);

		printf("%d\n",dis[n]);

		return 0;

	}

	int Q;

	scanf("%d",&Q);

	for(int i=1;i<=Q;i++)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		cur[y-1]|=(1<<(x-2));

	}

	memset(f,0x3f,sizeof(f));

	for(int i=2;i<=k+1;i++)Dijkstra(i);

	for(int S=1;S<1<<k;S++)

	{

		for(int i=1;i<=k;i++)

		{

			if(S&(1<<(i-1)))

			{

				for(int j=1;j<=k;j++)

				{

					if(!(S&(1<<(j-1)))&&(S&cur[j])==cur[j])

					{

						f[S|(1<<(j-1))][j]=min(f[S|(1<<(j-1))][j],f[S][i]+map[i][j]);

					}

				}

			}

		}

	}

	int ans=1<<30;

	for(int i=1;i<=k;i++)

	{

		ans=min(ans,f[(1<<k)-1][i]+g[i]);

	}

	printf("%d\n",ans);

	return 0;

}