#include<set>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 typedef long long ll;

 const int N = 5e4+;

 const int M = 5e5+;

 const int NK = ;

 const int inf = 2e9;

 ll read() {

     char c=getchar();

     ll f=,x=;

     while(!isdigit(c)) {

         if(c=='-') f=-; c=getchar();

     }

     while(isdigit(c))

         x=x*+c-'',c=getchar();

     return x*f;

 }

 struct Edge {

     int v,w,nxt;

 }e[M];

 int en=,front[N];

 void adde(int u,int v,int w)

 {

     e[++en]=(Edge){v,w,front[u]}; front[u]=en;

 }

 int n,m,K,bin[NK];

 int f[<<NK][NK];

 int dis[NK][N],a[N];

 queue<int> q; int inq[N];

 void spfa(int s) {

     memset(inq,,sizeof(inq));

     FOR(i,,n) dis[s][i]=inf;

     q.push(s); inq[s]=; dis[s][s]=;

     while(!q.empty()) {

         int u=q.front(); q.pop(); inq[u]=;

         trav(u,i) {

             int v=e[i].v;

             if(dis[s][v]>dis[s][u]+e[i].w) {

                 dis[s][v]=dis[s][u]+e[i].w;

                 if(!inq[v])

                     inq[v]=,q.push(v);

             }

         }

     }

 }

 int dp(int now,int u) {

     int& ans=f[now][u];

     if(ans>=) return ans;

     if(now==bin[K]-) return dis[u][n-];

     ans=inf;

     FOR(i,,K)

         if((now&a[i])==a[i])

             ans=min(ans,dp(now|bin[i-],i)+dis[u][i]);

     return ans;

 }

 int main()

 {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     bin[]=;

     FOR(i,,NK-) bin[i]=bin[i-]<<;

     n=read(),m=read(),K=read();

     FOR(i,,m) {

         int u=read(),v=read(),w=read();

         u--,v--;

         adde(u,v,w),adde(v,u,w);

     }

     FOR(i,,K) spfa(i);

     int x=read();

     while(x--) {

         int u=read(),v=read();

         a[v-]|=bin[u-];

     }

     memset(f,-,sizeof(f));

     printf("%d",dp(,));

     return ;

 }