BOJ 23807 두 단계 최단 경로 3

void solve(){
    ll N, M; cin >> N >> M;
    vector<vector<pll>> links(N+1);
    rep(i, 0, M){
        ll u, v, w; cin >> u >> v >> w;
        links[u].push_back({v, w});
        links[v].push_back({u, w});
    }
    int X, Z; cin >> X >> Z;

    vector<ll> dist_fromX(N+1, 1e18), dist_fromZ(N+1, 1e18);
    auto dijkstra = [&](ll start, vector<ll> &dist){
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        dist[start] = 0;
        pq.push({0, start});
        while(!pq.empty()){
            auto [cd, cur] = pq.top(); pq.pop();
            if(cd > dist[cur]) continue;
            for(auto [nxt, w] : links[cur]){
                ll nd = cd + w;
                if(nd < dist[nxt]){
                    dist[nxt] = nd;
                    pq.push({nd, nxt});
                }
            }
        }
    };
    dijkstra(X, dist_fromX);
    dijkstra(Z, dist_fromZ);

    int P; cin >> P;
    vector<int> cand(P);
    rep(i, 0, P) cin >> cand[i];

    ll ans = 1e18;
    for(int c2: cand){
        vector<ll> dist_fromC(N+1, 1e18);
        dijkstra(c2, dist_fromC);
        for(int c1: cand) for(int c3: cand){
            if(c1 == c2 || c2 == c3 || c1 == c3) continue;
            ans = min(ans, dist_fromX[c1] + dist_fromC[c1] + dist_fromC[c3] + dist_fromZ[c3]);
        }
    }
    if(ans >= 1e18) ans = -1;
    cout << ans;
}