#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll   = long long;
using ull  = unsigned long long;
using ld   = long double;

#if 0
#define int  ll
#define uint ull
#endif

/**
 *!Problem: Team
 * URL: https://infoarena.ro/problema/team
 * TL: 100 ms
 * ML: 20 MB
 *
 * Good Luck!
*/

struct state {
    int i, j, u, t;

    const bool operator<(const state &b) const { return this->t > b.t; }
};

inline void init() {
    int p, n, m;
    cin >> p >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1);
    for (int _ = 1; _ <= m; _++) {
        int i, j, c;
        cin >> i >> j >> c;

        adj[i].push_back({j, c});
        adj[j].push_back({i, c});
    }

    vector<int> dropoff(p + 1);
    for (int i = 1; i <= p; i++) { cin >> dropoff[i]; }

    vector<vector<vector<int>>> dp(
        p + 1, vector<vector<int>>(p + 1, vector<int>(n + 1, 1e9)));
    // dp[1][p][1] = 0;

    priority_queue<state> q;
    // q.push({1, p, 1, 0});

    for (int i = 1; i <= p; i++) {
        q.push({i, i, dropoff[i], 0});
        dp[i][i][dropoff[i]] = 0;
    }

    while (!q.empty()) {
        auto [i, j, u, t] = q.top();
        // cout << i << " " << j << " " << u << " " << t << '\n';
        q.pop();

        if (dp[i][j][u] < t) continue;

        for (auto &[v, c] : adj[u]) {
            if (t + c < dp[i][j][v]) {
                dp[i][j][v] = t + c;
                // q.push({i, j, v, t + c});
                // for (int k = i; k <= j; k++) {
                //     int l = k;
                //     while (l <= j && dropoff[l] != v) l++;
                //     l--;
                //     if (k <= l) {
                //         // dp[k][l][v] = 0;
                //         q.push({k, l, v, t + c});
                //         k = l;
                //     }
                // }
            }
        }

        for (int st = 1; st < p; st++) {
            for (int dr = st + 1; dr <= p; dr++) {
                for (int mid = st; mid < dr; mid++) {
                    int merge_cost = dp[st][mid][u] + dp[mid + 1][dr][u];

                    // cout << "? st = " << st << " mid = " << mid
                    //      << " dr = " << dr << " u = " << u
                    //      << " merge_cost = " << merge_cost
                    //      << " dp[st][dr][u] = " << dp[st][dr][u] << '\n';

                    if (merge_cost < dp[st][dr][u]) {
                        dp[st][dr][u] = merge_cost;
                        q.push({st, dr, u, dp[st][dr][u]});
                    }
                }
            }
        }
    }

    cout << dp[1][p][1] - 1 << '\n';
}
inline void tc() {}

#define FIO  1
#define FILE "team"

signed main() {
#if FIO
    freopen(FILE ".in", "r", stdin);
    freopen(FILE ".out", "w", stdout);
#endif
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    init();
    int tt;
    if (!(cin >> tt)) return 0;
    while (tt--) tc();
    return 0;
}