答案错的，保证dij正确

#include<bits/stdc++.h>
using namespace std;
const int N = 184760, M = 4e5 + 4;
inline int fastread() {
	int f = 1, x = 0;
	char ss = getchar();
	while (ss < '0' || ss > '9') {
		if (ss == '-') f = -1;
		ss = getchar();
	}
	while (ss >= '0' && ss <= '9') {
		x = (x << 1) + (x << 3) + (ss ^ 48);
		ss = getchar();
	}
	return f * x;
}
int n, m, k;
struct Edge {
	int to, nxt, w;
} e[M];
const int mm = 2e4 + 5;
int len, head[mm];
inline void In(int u, int v, int w) {
	e[++len] = {v, head[u], w};
	head[u] = len;
}
int q, x[mm];
int dis[25][mm];
struct Node {
	int v, d;
	bool operator < (const Node &a) const {
		return d > a.d;
	}
};
priority_queue<Node>p;
bool vis[mm];
inline void dij(int s) {
	for (int i = 1; i <= n; ++i) dis[s][i] = 0x3f3f3f3f, vis[i] = 0;
	dis[s][s] = 0;
	p.push({s, 0});
	while (!p.empty()) {
		int u = p.top().v;
		p.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i; i =  e[i].nxt) {
			int v = e[i].to;
			if (dis[s][v] > dis[s][u] + e[i].w) {
				dis[s][v] = dis[s][u] + e[i].w;
				if (!vis[v]) p.push({v, dis[s][v]});
			}
		}
	}
}
int dp[21][N][2], dy[1 << 21];
vector<int>num[21];
void read() {
	n = fastread(), m = fastread(), k = fastread();
	for (int i = 1, u, v, w; i <= m; ++i) {
		u = fastread(), v = fastread(), w = fastread();
		In(u, v, w), In(v, u, w);
	}
	for (int i = 1; i <= k + 1; ++i) dij(i);
	q = fastread();
	if (k == 0) return printf("%d", dis[1][n]), void();
	for (int i = 1; i <= q; ++i) {
		int f, l;
		f = fastread(), l = fastread();
		x[l - 1] |= 1 << (f - 1);
	}
	memset(dp, 0x3f, sizeof dp);
	int maxn = (1 << (k + 1)) - 1;
	for (int i = 1; i <= maxn; ++i) {
		int s = i, sum = 0;
		while (s) sum += s % 2, s /= 2;
		num[sum].push_back(i);
	}
	for (int i = 1; i <= k; ++k)
		for (auto j : num[i]) dy[num[i][j]] = j;
	for (int i = 1; i <= k; ++i) dp[i][1][1] = dis[1][i + 1];
	for (int i = 2; i < k; ++i) {
		for (auto j : num[i]) {
			int s = num[i][j];
			for (int u = 1; u <= k; ++k) {
				dp[u][j][i % 2] = 0x3f3f3f3f;
				if (!(s & (1 << u))) continue;
				for (int v = 1; v <= k; ++k) {
					if ((s & (1 << v))) continue;
					int sm = s | (1 << v);
					dp[v][dy[sm]][(i + 1) % 2] = min(dp[v][dy[sm]][(i + 1) % 2], dp[u][s][i % 2] + dis[u][v]);
				}
			}
		}
	}
	int minn = 0x3f3f3f3f;
	for (int i = 1; i <= k; ++i) {
		minn = min(minn, dp[i][maxn][n % 2] + dis[i + 1][n]);
	}
	printf("%d", minn);

}
int main() {
	read();
	return 0;
}