1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, rnk;
    DSU(int n = 0) { init(n); }
    void init(int n) {
        parent.resize(n + 1);
        rnk.assign(n + 1, 0);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
};

struct Edge { int u, v, c; };

struct RunResult {
    bool valid;
    int usedCross;
    long long sumPrime; // sum of (c + x * isCross)
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, w;
    if (!(cin >> n >> m >> k >> w)) return 0;

    vector<char> isSpecial(n + 1, 0);
    for (int i = 0; i < k; ++i) {
        int s; cin >> s;
        isSpecial[s] = 1;
    }

    vector<Edge> crossEdges, sameEdges;
    crossEdges.reserve(m); sameEdges.reserve(m);
    vector<pair<int,int>> allForConn; allForConn.reserve(m);

    for (int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        bool cross = (isSpecial[a] ^ isSpecial[b]);
        if (cross) crossEdges.push_back({a, b, c});
        else sameEdges.push_back({a, b, c});
        allForConn.push_back({a, b});
    }

    // Connectivity quick check
    {
        DSU dsu(n);
        for (auto &p : allForConn) dsu.unite(p.first, p.second);
        int root = dsu.find(1);
        for (int i = 2; i <= n; ++i) if (dsu.find(i) != root) { cout << -1 << '\n'; return 0; }
    }

    sort(crossEdges.begin(), crossEdges.end(), [](const Edge& a, const Edge& b){ return a.c < b.c; });
    sort(sameEdges.begin(), sameEdges.end(), [](const Edge& a, const Edge& b){ return a.c < b.c; });

    auto run = [&](int x, bool wantMaxCross) -> RunResult {
        DSU dsu(n);
        int i = 0, j = 0, cnt = 0, usedCross = 0;
        long long sumPrime = 0;
        const int S = (int)sameEdges.size();
        const int C = (int)crossEdges.size();
        while (cnt < n - 1 && (i < S || j < C)) {
            bool takeCross = false;
            if (i >= S) takeCross = true;
            else if (j >= C) takeCross = false;
            else {
                long long ks = sameEdges[i].c;
                long long kc = (long long)crossEdges[j].c + (long long)x;
                if (ks < kc) takeCross = false;
                else if (ks > kc) takeCross = true;
                else takeCross = wantMaxCross; // tie-break
            }
            if (!takeCross) {
                const Edge &e = sameEdges[i++];
                if (dsu.unite(e.u, e.v)) { cnt++; sumPrime += e.c; }
            } else {
                const Edge &e = crossEdges[j++];
                if (dsu.unite(e.u, e.v)) { cnt++; usedCross++; sumPrime += (long long)e.c + (long long)x; }
            }
        }
        if (cnt != n - 1) return {false, 0, 0};
        return {true, usedCross, sumPrime};
    };

    const int INF_X = 200000; // safely beyond max edge cost
    RunResult extremeMax = run(-INF_X, true);   // cross edges cheap -> maximize cross count
    RunResult extremeMin = run(+INF_X, false);  // cross edges expensive -> minimize cross count
    if (!extremeMax.valid || !extremeMin.valid) { cout << -1 << '\n'; return 0; }
    if (w < extremeMin.usedCross || w > extremeMax.usedCross) { cout << -1 << '\n'; return 0; }

    long long answer = -1;
    int lo = -INF_X, hi = INF_X;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        RunResult rMax = run(mid, true);
        RunResult rMin = run(mid, false);
        if (!rMax.valid || !rMin.valid) { cout << -1 << '\n'; return 0; }
        if (rMin.usedCross <= w && w <= rMax.usedCross) {
            answer = rMax.sumPrime - (long long)mid * (long long)w; // any MST' works
            break;
        }
        if (rMax.usedCross < w) hi = mid - 1; else lo = mid + 1;
    }

    cout << answer << '\n';
    return 0;
}