#include<bits/stdc++.h>

using namespace std;

#define MAXN 20010

#define MAXM 200010

#define MAXK 25

const int INF = 2e9;

const int MAXS =  << ;

int i,j,x,n,m,k,u,v,w,tot,g,ts,ans,Mask;

int head[MAXN],s[MAXK];

int dist[MAXK][MAXN],f[MAXS][MAXK];

bool visited[MAXN];

struct Edge

{

    int to,w,nxt;

} e[MAXM << ];

inline void addedge(int u,int v,int w)

{

    tot++;

    e[tot] = (Edge){v,w,head[u]};

    head[u] = tot;

}

inline void dijkstra(int s)

{

    int i,v,w;

    priority_queue< pair<int,int> > q;

    pair<int,int> cur;

    for (i = ; i <= n; i++)

    {

        dist[s][i] = INF;

        visited[i] = false;

    }

    dist[s][s] = ;

    q.push(make_pair(,s));

    while (!q.empty())

    {

        cur = q.top();

        q.pop();

        if (visited[cur.second]) continue;

        visited[cur.second] = true;

        for (i = head[cur.second]; i; i = e[i].nxt)

        {

            v = e[i].to;

            w = e[i].w;

            if (dist[s][cur.second] + w < dist[s][v])

            {

                dist[s][v] = dist[s][cur.second] + w;

                q.push(make_pair(-dist[s][v],v));

            }

        }

    }

}

int main()

{

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

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

    {

        scanf("%d%d%d",&u,&v,&w);

        addedge(u,v,w);

        addedge(v,u,w);

    }

    scanf("%d",&g);

    for (i = ; i <= g; i++)

    {

        scanf("%d%d",&u,&v);

        s[v] |= ( << (u - ));

    }

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

    Mask = ( << k) - ;

    for (i = ; i <= Mask; i++)

    {

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

        {

            f[i][j] = INF;

        }

    }

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

    {

        if (!s[i])

            f[ << (i - )][i] = dist[i][];

    }

    f[][] = ;

    for (i = ; i <= Mask; i++)

    {

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

        {

            for (x = ; x <= k + ; x++)

            {

                ts = i | ( << (x - ));

                if (((s[x] & i) == s[x]) && f[i][j] + dist[j][x] < f[ts][x])

                    f[ts][x] = f[i][j] + dist[j][x];

            }

        }

    }

    ans = INF;

    for (i = ; i <= k + ; i++) ans = min(ans,f[Mask][i] + dist[i][n]);

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

    return ;

}