#include <cstdio>#include <cstdlib>#include <cmath>#include <set>#include <stack>#include <vector>#include <sstream>#include <cstring>#include <string>#include <map>#include <queue>#include <algorithm>#include <iostream>#define FFI freopen("in.txt", "r", stdin)#define maxn 1000100#define INF 0x3f3f3f3f#define inf 10000000#define MOD 1000000007#define ULL unsigned long long#define LL long long#define _setm(houge) memset(houge, INF, sizeof(houge))#define _setf(houge) memset(houge, -1, sizeof(houge))#define _clear(houge) memset(houge, 0, sizeof(houge))using namespace std;int g[10][10], r[10][10];int dp[1500][10];int a[20], n, k;int main() {	// FFI;	int t;	scanf("%d", &t);	while(t --) {		scanf("%d", &n);		for(int i = 1; i <= n; ++ i) {			for(int j = 1; j <= n; ++ j) {				scanf("%d%d", &g[i][j], &r[i][j]);			}		}		scanf("%d", &k);		for(int i = 0; i < k; ++ i) {			scanf("%d", &a[i]);		}		_setm(dp);		for(int i = 0; i < k; ++ i) {			dp[1<<i][a[i]] = 0;		}		int tot = (1<<k);		for(int s = 0; s < tot; ++ s) {			for(int i = 1; i <= n; ++ i) {				if(dp[s][i] == INF) continue;				for(int s2 = 0; s2 < tot; ++ s2) {					if(s&s2) continue;					for(int j = 1; j <= n; ++ j) {						if(dp[s2][j] == INF) continue;						int S = s|s2, now = g[i][j], v = r[i][j];						int now2 = g[j][i], v2 = r[j][i];						dp[S][now] = min(dp[S][now], dp[s][i]+dp[s2][j]+v);						dp[S][now2] = min(dp[S][now2], dp[s][i]+dp[s2][j]+v2);					}				}			}		}		int ans = INF;		for(int i = 1; i <= n; ++ i) {			ans = min(ans, dp[tot-1][i]);		}		printf("%d\n", ans);		char a[2];		scanf("%s", a);	}	return 0;}