本题考察的是最小生成树Kruskal算法，但从题目给出的数据范围看，无法把整张图都建出来，然后一次性求出结果，只能分步计算。

解题思路：
1、由于不同行星内部的图结构都是相同的，所以可以先在行星内部求出局部的最小生成树，并记录所有的有效权值（后面第3步会用到），累加所有删掉的权值，由于有N个星球，所以答案的权值要乘N。
2、接下来把每个行星当做一个独立的点，然后考虑行星间的最小生成树，根据题意，每次给出的两个行星间的路径，都表示两个行星间有M条重边，累加答案的时候注意这点。
3、最后将前面两步求的最小生成树的结果作为一个整体继续考虑，并求得最终的最小生成树，但考虑到数据范围，这一步依旧无法直接使用Kruskal。在第2步中，每对行星间我们只保留了唯一的一条路径，那么是否可以保留多条路径呢？其实只要行星内部的路径权值大于行星间的路径权值，就可以用一条行星间的路径替代行星内部的路径，这样依然能保证是个树形结构。最后就是怎么快速求这部分的答案了，把第1步中保存的有效权值进行排序，使用二分查找和前缀和即可，整体时间复杂度O(NlogN)。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m, k, t;
int p[N];
struct Edge
{
    int u, v, w;
    bool operator < (const Edge &T) const {
        return w < T.w;
    }
} edges[N];
int w1[N], w2[N];
long s[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

long kruskal(int n, int m, int w[N])
{
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(edges, edges + m);

    long ans = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        auto e = edges[i];
        int pu = find(e.u), pv = find(e.v);
        if (pu != pv) p[pu] = pv, w[++cnt] = e.w;
        else ans += e.w;
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k >> t;

    for (int i = 0; i < k; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }

    long ans = kruskal(m, k, w1) * n;

    long sum = 0;
    for (int i = 0; i < t; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
        sum += w;
    }

    ans += kruskal(n, t, w2) + sum * (m - 1);

    sort(w1 + 1, w1 + m, greater<int>());
    for (int i = 1; i < m; i++) s[i] = s[i - 1] + w1[i];

    for (int i = 1; i < n; i++) {
        int cnt = lower_bound(w1 + 1, w1 + m, w2[i], greater<int>()) - w1 - 1;
        ans += s[cnt] - (long) w2[i] * cnt;
    }

    cout << ans;
    return 0;
}