#include <bits/stdc++.h>
using namespace std;
 
int n, m, reaction[8][8], power[8][8], tube[12], dp[1<<12][12];
 
int solve(int mask, int prev){
 if(mask == ((1<<m)-1)) return 0;
 if(dp[mask][prev] != -1) return dp[mask][prev];
 int ans = 1<<30, res;
 for(int i = 0; i<m; i++){
  res = 0;
  if(!(mask & (1<<i))){
   res += power[prev][i] + solve(mask | (1<<i), reaction[prev][i]);
  }
  ans = min(ans, res);
 }
 return dp[mask][prev] = ans;
}
 
int main() {
 int t;
 string str;
 scanf("%d", &t);
 for(int i = 1; i<=t; i++){
  scanf("%d", &n); 
  for(int j = 0; j<n; j++){
   for(int k = 0; k<n; k++){
    scanf("%d %d", &reaction[j][k], &power[j][k]); reaction[j][k]--;
   }
  }
  scanf("%d", &m);
  for(int j = 0; j<m; j++){
   scanf("%d", &tube[j]); tube[j]--;
  }
 
  int ans = 1<<30;
  for(int j = 0; j<m; j++){
   for(int k = j+1; k<m; k++){
   	memset(dp,-1,sizeof(dp));
   	int x = tube[j], y = tube[k];
    ans = min(ans,power[x][y] + solve(0 | (1<<j) | (1<<k), reaction[x][y]));
   }
  }
  cin >> str;
  printf("%d\n", ans);
 }
 cin >> str;
 return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbiwgbSwgcmVhY3Rpb25bOF1bOF0sIHBvd2VyWzhdWzhdLCB0dWJlWzEyXSwgZHBbMTw8MTJdWzEyXTsKCmludCBzb2x2ZShpbnQgbWFzaywgaW50IHByZXYpewogaWYobWFzayA9PSAoKDE8PG0pLTEpKSByZXR1cm4gMDsKIGlmKGRwW21hc2tdW3ByZXZdICE9IC0xKSByZXR1cm4gZHBbbWFza11bcHJldl07CiBpbnQgYW5zID0gMTw8MzAsIHJlczsKIGZvcihpbnQgaSA9IDA7IGk8bTsgaSsrKXsKICByZXMgPSAwOwogIGlmKCEobWFzayAmICgxPDxpKSkpewogICByZXMgKz0gcG93ZXJbcHJldl1baV0gKyBzb2x2ZShtYXNrIHwgKDE8PGkpLCByZWFjdGlvbltwcmV2XVtpXSk7CiAgfQogIGFucyA9IG1pbihhbnMsIHJlcyk7CiB9CiByZXR1cm4gZHBbbWFza11bcHJldl0gPSBhbnM7Cn0KCmludCBtYWluKCkgewogaW50IHQ7CiBzdHJpbmcgc3RyOwogc2NhbmYoIiVkIiwgJnQpOwogZm9yKGludCBpID0gMTsgaTw9dDsgaSsrKXsKICBzY2FuZigiJWQiLCAmbik7IAogIGZvcihpbnQgaiA9IDA7IGo8bjsgaisrKXsKICAgZm9yKGludCBrID0gMDsgazxuOyBrKyspewogICAgc2NhbmYoIiVkICVkIiwgJnJlYWN0aW9uW2pdW2tdLCAmcG93ZXJbal1ba10pOyByZWFjdGlvbltqXVtrXS0tOwogICB9CiAgfQogIHNjYW5mKCIlZCIsICZtKTsKICBmb3IoaW50IGogPSAwOyBqPG07IGorKyl7CiAgIHNjYW5mKCIlZCIsICZ0dWJlW2pdKTsgdHViZVtqXS0tOwogIH0KICAKICBpbnQgYW5zID0gMTw8MzA7CiAgZm9yKGludCBqID0gMDsgajxtOyBqKyspewogICBmb3IoaW50IGsgPSBqKzE7IGs8bTsgaysrKXsKICAgCW1lbXNldChkcCwtMSxzaXplb2YoZHApKTsKICAgCWludCB4ID0gdHViZVtqXSwgeSA9IHR1YmVba107CiAgICBhbnMgPSBtaW4oYW5zLHBvd2VyW3hdW3ldICsgc29sdmUoMCB8ICgxPDxqKSB8ICgxPDxrKSwgcmVhY3Rpb25beF1beV0pKTsKICAgfQogIH0KICBjaW4gPj4gc3RyOwogIHByaW50ZigiJWRcbiIsIGFucyk7CiB9CiBjaW4gPj4gc3RyOwogcmV0dXJuIDA7Cn0=

MgozCjEgIDAKMyAgLTEwCjMgIDMwMDAKMyAgLTEwCjIgIDAKMSAgLTUwMAozICAzMDAwCjEgIC01MDAKMyAgMAo0CjEgIDIgIDIgIDMKLwozCjEgIDAKMyAgNTAwCjMgIC0yNTAKMyAgNTAwCjIgIDAKMSAgMTAKMyAgLTI1MAoxICAxMDAKMyAgMAo2CjEgIDEgIDEgIDIgIDIgIDMKLg==

2
3
1  0
3  -10
3  3000
3  -10
2  0
1  -500
3  3000
1  -500
3  0
4
1  2  2  3
/
3
1  0
3  500
3  -250
3  500
2  0
1  10
3  -250
1  100
3  0
6
1  1  1  2  2  3
.