Secret Message

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = (1LL << 62);
const ll NEG = -(1LL << 60);

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct DSU {
    vector<int> p, sz;

    DSU(int n = 0) { init(n); }

    void init(int n) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }

    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Edge {
    int u, v, id;
    ll w;
};

struct Best {
    ll a, b;
    Best(ll x = NEG, ll y = NEG) : a(x), b(y) {}
};

Best mergeBest(Best x, Best y) {
    array<ll, 4> vals = {x.a, x.b, y.a, y.b};
    sort(vals.begin(), vals.end(), greater<ll>());
    return Best(vals[0], vals[1]);
}

struct SegTree {
    int n;
    vector<Best> st;

    void init(const vector<ll>& base) {
        n = 1;
        while (n < (int)base.size()) n <<= 1;
        st.assign(2 * n, Best());
        for (int i = 0; i < (int)base.size(); i++) st[n + i] = Best(base[i], NEG);
        for (int i = n - 1; i >= 1; i--) st[i] = mergeBest(st[i << 1], st[i << 1 | 1]);
    }

    Best query(int l, int r) const {
        if (l > r) return Best();
        l += n;
        r += n;
        Best left, right;
        while (l <= r) {
            if (l & 1) left = mergeBest(left, st[l++]);
            if (!(r & 1)) right = mergeBest(st[r--], right);
            l >>= 1;
            r >>= 1;
        }
        return mergeBest(left, right);
    }
};

struct HLD {
    int n, cur;
    vector<vector<pair<int, ll>>> adj;
    vector<int> parent, depth, heavy, head, pos, sz;
    vector<ll> parW;
    SegTree seg;

    HLD(const vector<vector<pair<int, ll>>>& g) { init(g); }

    void init(const vector<vector<pair<int, ll>>>& g) {
        adj = g;
        n = adj.size();
        parent.assign(n, -1);
        depth.assign(n, 0);
        heavy.assign(n, -1);
        head.assign(n, 0);
        pos.assign(n, 0);
        sz.assign(n, 1);
        parW.assign(n, NEG);

        vector<int> order;
        order.reserve(n);
        vector<int> st = {0};
        parent[0] = -2;
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            order.push_back(v);
            for (auto [to, w] : adj[v]) {
                if (to == parent[v]) continue;
                parent[to] = v;
                depth[to] = depth[v] + 1;
                parW[to] = w;
                st.push_back(to);
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            int v = order[i];
            int bestSize = 0;
            sz[v] = 1;
            for (auto [to, w] : adj[v]) {
                if (parent[to] != v) continue;
                sz[v] += sz[to];
                if (sz[to] > bestSize) {
                    bestSize = sz[to];
                    heavy[v] = to;
                }
            }
        }

        vector<ll> base(n, NEG);
        cur = 0;
        vector<pair<int, int>> starts = {{0, 0}};
        while (!starts.empty()) {
            auto [v, h] = starts.back();
            starts.pop_back();
            for (int x = v; x != -1; x = heavy[x]) {
                head[x] = h;
                pos[x] = cur;
                base[cur++] = parW[x];
                for (auto [to, w] : adj[x]) {
                    if (parent[to] == x && to != heavy[x]) starts.push_back({to, to});
                }
            }
        }
        seg.init(base);
    }

    vector<pair<int, int>> pathIntervals(int a, int b) const {
        vector<pair<int, int>> res;
        while (head[a] != head[b]) {
            if (depth[head[a]] < depth[head[b]]) swap(a, b);
            res.push_back({pos[head[a]], pos[a]});
            a = parent[head[a]];
        }
        if (depth[a] > depth[b]) swap(a, b);
        if (pos[a] + 1 <= pos[b]) res.push_back({pos[a] + 1, pos[b]});
        return res;
    }

    vector<pair<int, int>> normalize(vector<pair<int, int>> v) const {
        sort(v.begin(), v.end());
        vector<pair<int, int>> res;
        for (auto [l, r] : v) {
            if (l > r) continue;
            if (res.empty() || l > res.back().second + 1) res.push_back({l, r});
            else res.back().second = max(res.back().second, r);
        }
        return res;
    }

    ll outsidePathMax(int a, int b) const {
        auto ints = normalize(pathIntervals(a, b));
        Best ans;
        int last = 0;
        for (auto [l, r] : ints) {
            if (last < l) ans = mergeBest(ans, seg.query(last, l - 1));
            last = max(last, r + 1);
        }
        if (last < n) ans = mergeBest(ans, seg.query(last, n - 1));
        return ans.a;
    }

    Best pathIntersectionBest(int a, int b, int c, int d) const {
        auto x = normalize(pathIntervals(a, b));
        auto y = normalize(pathIntervals(c, d));
        Best ans;
        int i = 0, j = 0;
        while (i < (int)x.size() && j < (int)y.size()) {
            int l = max(x[i].first, y[j].first);
            int r = min(x[i].second, y[j].second);
            if (l <= r) ans = mergeBest(ans, seg.query(l, r));
            if (x[i].second < y[j].second) i++;
            else j++;
        }
        return ans;
    }
};

int main() {
    setIO();

    int tc;
    cin >> tc;
    while (tc--) {
        int n, m;
        cin >> n >> m;
        vector<Edge> edges(m);
        for (int i = 0; i < m; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
            --edges[i].u;
            --edges[i].v;
            edges[i].id = i;
        }

        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            if (a.w != b.w) return a.w < b.w;
            return a.id < b.id;
        });

        DSU dsu(n);
        ll baseSum = 0;
        bool isTree = true;
        for (int i = 0; i < n - 1; i++) {
            baseSum += edges[i].w;
            if (!dsu.unite(edges[i].u, edges[i].v)) isTree = false;
        }

        if (!isTree) {
            cout << baseSum << '\n';
            continue;
        }

        vector<vector<pair<int, ll>>> adj(n);
        for (int i = 0; i < n - 1; i++) {
            auto &e = edges[i];
            adj[e.u].push_back({e.v, e.w});
            adj[e.v].push_back({e.u, e.w});
        }

        HLD hld(adj);
        ll ans = INF;

        for (int i = n - 1; i < m; i++) {
            auto &e = edges[i];
            ll removed = hld.outsidePathMax(e.u, e.v);
            if (removed != NEG) ans = min(ans, baseSum + e.w - removed);
        }

        if (m - (n - 1) >= 2) {
            auto &a = edges[n - 1];
            auto &b = edges[n];
            Best common = hld.pathIntersectionBest(a.u, a.v, b.u, b.v);
            if (common.b != NEG) ans = min(ans, baseSum + a.w + b.w - common.a - common.b);
        }

        cout << (ans == INF ? -1 : ans) << '\n';
    }
}