#include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=,K=,inf=0x3f3f3f3f;

 struct a{int node,dist;};

 bool operator < (a x,a y)

 {

     return x.dist>y.dist;

 }

 priority_queue<a> hp;

 int dis[N],vis[N],ss[K],dp[(<<)+][K];

 int p[N],noww[*M],goal[*M],val[*M],mat[K][K];

 int n,m,k,c,t1,t2,t3,cnt,len,all,ans=inf;

 void link(int f,int t,int v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,val[cnt]=v;

 }

 void Dijkstra(int s)

 {

     memset(vis,,sizeof vis);

     memset(dis,0x3f,sizeof dis);

     dis[s]=,hp.push((a){s,});

     while(!hp.empty())

     {

         a tt=hp.top(); hp.pop(); int tn=tt.node;

         if(vis[tn]) continue ; vis[tn]=true;

         for(int i=p[tn];i;i=noww[i])

             if(dis[goal[i]]>dis[tn]+val[i])

                 dis[goal[i]]=dis[tn]+val[i],hp.push((a){goal[i],dis[goal[i]]});

     }

 }

 int ins(int x)

 {

     return <<(x-);

 }

 int main ()

 {

     scanf("%d%d%d",&n,&m,&k),all=(<<k)-;

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

     {

         scanf("%d%d%d",&t1,&t2,&t3);

         link(t1,t2,t3),link(t2,t1,t3);

     }

     scanf("%d",&c);

     for(int i=;i<=c;i++)

         scanf("%d%d",&t1,&t2),ss[t2]|=ins(t1);

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

     {

         Dijkstra(i);

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

             mat[i][j]=dis[j]; mat[i][]=dis[n];

     }

     memset(dp,0x3f,sizeof dp),dp[][]=;

     for(int i=;i<=all;i++)

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

             if(dp[i][j]!=inf)

                 for(int h=;h<=k+;h++)

                     if((i&ss[h])==ss[h])

                         dp[i|ins(h)][h]=min(dp[i|ins(h)][h],dp[i][j]+mat[j][h]);

     for(int i=;i<=k+;i++) ans=min(ans,dp[all][i]+mat[i][]);

     printf("%d",ans);

     return ;

 }