//Oh? You're Approaching Me?

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


//#pragma GCC optimize("O3,unroll-loops")
#define migmig     		ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;


const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int inf = 1e9 + 90;
const int maxLG = 20;
const int SQ = 350;

ll n, m, dist[MAXN];
vector<pll> G[MAXN];
bool mark[MAXN];
set<pii> se;
ll MST = 0;

inline void add(int v) {
	for (auto [u, w] : G[v]) {
		if (!mark[u]) {
	      se.erase({dist[u], u});
	      se.insert({(dist[u] = w), u});
    	}
	}
}


inline void prim() {
	dist[1] = 0;
	add(1);
	se.insert({0, 1});
	for (int i = 1; i <= n; i++) {
		if (se.empty()) {
			return;
		}
		auto tmp = *(se.begin());
		ll v = tmp.S;
		MST += tmp.F;
		se.erase(tmp);
		add(v);
		mark[v] = 1;
	}
}

int main() {
	migmig;
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		memset(dist, 63, sizeof dist);
		for (int i = 1; i <= m; i++) {
			ll v, u, w;
			cin >> v >> u >> w;
			G[v].pb({u, w});
		}
		prim();
//		deb(MST);
		cout << MST << endl;
		MST = 0;
		for (int i = 1; i <= n; i++)
			G[i].cl();
		se.cl();
		memset(mark, false, sizeof mark);
	}
}

/*
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
*/