あるチェックポイントから次のチェックポイントへ向かうとき、その経路や所要時間はこれまでやこれからの移動に影響されません。 よって、チェックポイント間の移動はそれぞれ独立に最短経路で行うべきです。 チェックポイントの個数 \(K\) が小さいため、チェックポイントに到達するたびに次のチェックポイントへの最短経路をダイクストラ法などを用いて計算すると、この問題を十分高速に解くことができます。

時間計算量は \(O(K(N+M)\log N)\) などになります。 チェックポイントの重複を取り除いたり、ダイクストラ法を用いるのを \(2\) チェックポイントに \(1\) 回とする（前のチェックポイントから来る最短経路と、次のチェックポイントへ行く最短経路を同時に求める）ことで定数倍を抑えることもできます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <optional>
#include <print>
using namespace std;

int main(){
    int N, M, K;
    cin >> N >> M >> K;

    // グラフを隣接リストの形式で持っておく
    vector<vector<pair<int, int>>> edges(N);
    for (int i = 0; i < M; ++i) {
        int u, v, t;
        cin >> u >> v >> t;
        --u; // 地点の番号は 0-indexed にしておく
        --v;
        edges[u].emplace_back(v, t);
        edges[v].emplace_back(u, t);
    }

    // ダイクストラ法で最短距離を求める
    constexpr long inf = numeric_limits<long>::max();
    auto shortest_path_distance = [&](int from, int to) -> optional<long> {
        vector<long> distance(N, inf);
        
        priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
        pq.emplace(distance[from] = 0, from);

        while (!pq.empty()) {
            auto [d, now] = pq.top();
            pq.pop();

            if (now == to) {
                return d;
            }

            for (auto [next, cost] : edges[now]) {
                if (distance[next] > d + cost) {
                    pq.emplace(distance[next] = d + cost, next);
                }
            }
        }

        // 連結でなければ到達できない
        return nullopt;
    };

    vector<int> P(K);
    for (int& p : P) {
        cin >> p;
        --p; // 0-indexed にしておく
    }
    P.emplace(P.begin(), 0); // スタート地点と
    P.emplace_back(N - 1); // ゴール地点を入れておく

    long time_sum = 0;
    for (auto [now, next] : P | views::adjacent<2>) { // 隣接する 2 つのチェックポイント（+ スタート, ゴール）について、
        auto distance = shortest_path_distance(now, next); // 最短距離を求める
        if (distance.has_value()) { // now から next に移動できるなら
            time_sum += distance.value(); // 答えに最短距離を足す
        } else { // できないなら
            cout << "-1" << endl; // -1 を出力して
            return 0; // 終了
        }
    }

    // 答えを出力
    cout << time_sum << endl;

    return 0;
}

from heapq import heappush, heappop


N, M, K = map(int, input().split())

# グラフを隣接リストの形式で持っておく
edges = [[] for _ in range(N)]
for _ in range(M):
    u, v, t = map(int, input().split())
    u -= 1 # 地点の番号は 0-indexed にしておく
    v -= 1
    edges[u].append((v, t))
    edges[v].append((u, t))

# ダイクストラ法で最短距離を求める
def shortest_path_distance(start, goal):
    distance = [10 ** 15 for _ in range(N)]
    distance[start] = 0

    heap = []
    heappush(heap, (0, start))

    while len(heap) > 0:
        d, now = heappop(heap)
        if now == goal:
            return d
        for next, cost in edges[now]:
            if distance[next] > d + cost:
                distance[next] = d + cost
                heappush(heap, (d + cost, next))

    # 連結でなければ到達できない
    return None

P = [1] + list(map(int, input().split())) + [N] # スタート地点とゴール地点を入れておく
P = [p - 1 for p in P] # 0-indexed にしておく

time_sum = 0
for now, next in zip(P, P[1:]): # 隣接する 2 つのチェックポイント（+ スタート, ゴール）について、
    distance = shortest_path_distance(now, next) # 最短距離を求める
    if distance is not None: # now から next に移動できるなら
        time_sum += distance # 答えに最短距離を足す
    else: # できないなら
        print(-1) # -1 を出力して
        break # ループを抜ける
else: # すべて移動できたら
    print(time_sum) # 合計を出力