#include <bits/stdc++.h>

#define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define sz(s) (int)(s).size()
#define all(s) (s).begin(),(s).end()
using namespace std;

void File();

void sol();

const int N = 1e5 + 5;
int idx[N];

int main() {
    boAshraf
    File();
    int t = 1;
    cin >> t;
    while (t--) {
        sol();
    }
    return 0;
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    vector<vector<pair<int, int>>> rev_adj(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        rev_adj[v].emplace_back(u, w);
    }
    int k;
    cin >> k;
    vector<int> imp(k);
    for (int i = 0; i < k; i++) {
        cin >> imp[i];
        idx[imp[i]] = i;
    }
    // from u to k[i]
    vector<vector<ll>> dist_from(k, vector<ll>(n + 1, 1e15));
    // from k[i] to u
    vector<vector<ll>> dist_to(k, vector<ll>(n + 1, 1e15));
    for (int i = 0; i < k; ++i) {
        {
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
            dist_to[i][imp[i]] = 0;
            pq.emplace(0, imp[i]);
            while (!pq.empty()) {
                auto [cost, u] = pq.top();
                pq.pop();
                if (dist_to[i][u] != cost)continue;
                for (auto [v, w]: adj[u]) {
                    if (dist_to[i][v] > cost + w) {
                        dist_to[i][v] = cost + w;
                        pq.emplace(dist_to[i][v], v);
                    }
                }
            }
        }
        {
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
            dist_from[i][imp[i]] = 0;
            pq.emplace(0, imp[i]);
            while (!pq.empty()) {
                auto [cost, u] = pq.top();
                pq.pop();
                if (dist_from[i][u] != cost)continue;
                for (auto [v, w]: rev_adj[u]) {
                    if (dist_from[i][v] > cost + w) {
                        dist_from[i][v] = cost + w;
                        pq.emplace(dist_from[i][v], v);
                    }
                }
            }
        }
    }
    vector<vector<vector<ll>>> dp(k, vector<vector<ll>>(k, vector<ll>(1 << k, -1)));
    int tot = (1 << k) - 1;
    auto rec = [&](auto &self, int last, int to, int mask)->ll {
        if (mask == tot)return 0;
        if (last == to)return 1e18;
        ll &ret = dp[last][to][mask];
        if (~ret)return ret;
        ret = 1e15;
        for (int i = 0; i < k; i++) {
            if ((mask >> i) & 1)continue;
            ret = min(ret, self(self, i, to, mask | (1 << i)) + dist_to[last][imp[i]]);
        }
        return ret;
    };
    int q;
    cin >> q;
    while (q--) {
        int s, e;
        cin >> s >> e;
        ll ans = 1e15;
        if (k == 1) {
            ans = dist_from[0][s] + dist_to[0][e];
        } else {
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    if(i==j)continue;
                    ll c=dist_from[i][s]+dist_to[j][e]+rec(rec,i,j,1<<i);
                    ans=min(ans,c);
                }
            }
        }
        cout << ans << '\n';
    }
}

void File() {
// #ifndef ONLINE_JUDGE
    freopen("strongly.in", "r", stdin);
    // freopen("output.txt", "w", stdout);
// #endif
}