#include <bits/stdc++.h>

using i64 = long long;

const int inf = 2e9;

void solve(){
    int n, m;
    std::cin >> n >> m;
    std::vector adj(n + 1, std::vector<std::pair<int, int> >());
    auto go = [&]() {
        std::vector<int> vis(n + 1);
        std::vector<int> dis(n + 1, inf);
        dis[1] = 0;
        std::priority_queue<std::pair<int, int> > pq;
        pq.push({0, 1});
        i64 res = 0;
        while (not pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (vis[u])
                continue;
            vis[u] = 1;
            res -= d;
            for (auto [v, w] : adj[u]) {
                if (not vis[v] and dis[v] > w) {
                    dis[v] = w;
                    pq.push({-w, v});
                }
            }
        }
        if (std::count(vis.begin() + 1, vis.end(), 0) > 0)
            return i64(1e18);
        return res;
    };

    int x, y, z;
    std::vector<std::tuple<int, int, int> > edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        if (u > v) {
            std::tie(x, y, z) = std::make_tuple(u, v, w);
            continue;
        }
        edges.push_back({u, v, w});
        adj[u].push_back({v, w});
    }
    i64 ans = go();
    for (int i = 1; i <= n; i += 1) {
        adj[i].clear();
    }
    for (auto [u, v, w] : edges) {
        if (v == y) continue;
        // std::cerr << u << " " << v << " " << w << "\n";
        adj[u].push_back({v, w});
    }
    // std::cerr << x << " " << y << " " << z << "\n";
    adj[x].push_back({y, z});
    ans = std::min(ans, go());
    std::cout << ans << '\n';
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}