rt，目前开 C++98 过了，C++14 和 C++20 都 TLE on #28。

复杂度为 $O(n\log^2 n)$，使用了 Boruvka 和线段树。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 1e5 + 5;

struct node{
    int l, r, a, b;
}ss[maxn];
int a1[maxn << 1], fa[maxn], lnk[maxn], sz[maxn];
ll v[maxn][2], w[maxn];
int find(int x){
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    if(sz[x] > sz[y]) swap(x, y);
    fa[x] = y, sz[y] += sz[x];
}

namespace seg{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
int id0[maxn << 3], id0_[maxn << 3], id1[maxn << 3], id1_[maxn << 3];
void build(int x, int l, int r){
    id0[x] = id0_[x] = id1[x] = id1_[x] = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(l(x), l, mid), build(r(x), mid + 1, r);
}
void update(int x, int l, int r, int ql, int qr, int id, int tp){
    if(ql <= l && r <= qr){
        if(find(id) == find(id0[x])){
            if(v[id][tp] < v[id0[x]][tp]) id0[x] = id;
        }else{
            if(v[id][tp] < v[id0[x]][tp]) id0_[x] = id0[x], id0[x] = id;
            else if(v[id][tp] < v[id0_[x]][tp]) id0_[x] = id;
        }
        return;
    }
    if(find(id) == find(id1[x])){
        if(v[id][tp] < v[id1[x]][tp]) id1[x] = id;
    }else{
        if(v[id][tp] < v[id1[x]][tp]) id1_[x] = id1[x], id1[x] = id;
        else if(v[id][tp] < v[id1_[x]][tp]) id1_[x] = id;
    }
    int mid = l + r >> 1;
    if(ql <= mid) update(l(x), l, mid, ql, qr, id, tp);
    if(qr > mid) update(r(x), mid + 1, r, ql, qr, id, tp);
}
int query(int x, int l, int r, int ql, int qr, int id, int tp){
    int res = 0;
    if(find(id) == find(id0[x])){
        if(v[id0_[x]][tp] < v[res][tp]) res = id0_[x];
    }else{
        if(v[id0[x]][tp] < v[res][tp]) res = id0[x];
    }
    if(ql <= l && r <= qr){
        if(find(id) == find(id1[x])){
            if(v[id1_[x]][tp] < v[res][tp]) res = id1_[x];
        }else{
            if(v[id1[x]][tp] < v[res][tp]) res = id1[x];
        }
        return res;
    }
    int mid = l + r >> 1;
    if(ql <= mid){
        int lres = query(l(x), l, mid, ql, qr, id, tp);
        if(v[lres][tp] < v[res][tp]) res = lres;
    }
    if(qr > mid){
        int rres = query(r(x), mid + 1, r, ql, qr, id, tp);
        if(v[rres][tp] < v[res][tp]) res = rres;
    }
    return res;
}}
inline int read(){
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x;
}

bool cmp(node x, node y){
    return x.b < y.b;
}

int main(){
    freopen("P11134.in", "r", stdin);
    freopen("P11134.out", "w", stdout);
    int T = read();
    while(T --){
        int n = read();
        for(int i = 1; i <= n; i ++){
            ss[i].l = read(), ss[i].r = read(), ss[i].a = read(), ss[i].b = read();
            a1[i * 2 - 1] = ss[i].l, a1[i * 2] = ss[i].r;
        }
        sort(a1 + 1, a1 + n * 2 + 1);
        int m = unique(a1 + 1, a1 + n * 2 + 1) - a1 - 1;
        for(int i = 1; i <= n; i ++) ss[i].l = lower_bound(a1 + 1, a1 + m + 1, ss[i].l) - a1, ss[i].r = lower_bound(a1 + 1, a1 + m + 1, ss[i].r) - a1;
        sort(ss + 1, ss + n + 1, cmp);
        for(int i = 1; i <= n; i ++) v[i][0] = ss[i].a + ss[i].b, v[i][1] = ss[i].a - ss[i].b, fa[i] = i, sz[i] = 1;
        v[0][0] = v[0][1] = (ll)1e18;
        ll ans = 0;
        int cnt = 0;
        while(1){
            for(int i = 0; i <= n; i ++) w[i] = (ll)1e18, lnk[i] = 0;
            seg::build(1, 1, m);
            for(int i = 1; i <= n; i ++){
                int res = seg::query(1, 1, m, ss[i].l, ss[i].r, i, 1);
                int x = find(i), y = find(res);
                if(y && x != y){
                    ll nw = v[i][0] + v[res][1];
                    if(nw < w[x]) w[x] = nw, lnk[x] = y;
                    if(nw < w[y]) w[y] = nw, lnk[y] = x;
                }
                seg::update(1, 1, m, ss[i].l, ss[i].r, i, 1);
            }
            seg::build(1, 1, m);
            for(int i = n; i >= 1; i --){
                int res = seg::query(1, 1, m, ss[i].l, ss[i].r, i, 0);
                int x = find(i), y = find(res);
                if(y && x != y){
                    ll nw = v[i][1] + v[res][0];
                    if(nw < w[x]) w[x] = nw, lnk[x] = y;
                    if(nw < w[y]) w[y] = nw, lnk[y] = x;
                }
                seg::update(1, 1, m, ss[i].l, ss[i].r, i, 0);
            }
            bool fl = false;
            for(int i = 1; i <= n; i ++){
                int x = find(i), y = find(lnk[x]);
                if(y && x != y && w[x] < (ll)1e18){
                    fl = true;
                    ans += w[x], cnt ++;
                    merge(x, y);
                }
            }
            if(!fl) break;
        }
        if(cnt == n - 1) printf("%lld\n", ans);
        else printf("-1\n");
    }
    return 0;
}