//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;

int n, m, dist[MAXN];
vector<pii> G[MAXN];
bitset<MAXN> vis;
set<pii> se;
ll MST = 0;

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


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());
		int v = tmp.S;
		MST += tmp.F;
		se.erase(tmp);
		add(v);
		vis[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++) {
			int v, u, w;
			cin >> v >> u >> w;
			G[v].pb({u, w});
	//		G[u].pb({v, w});
		}
		prim();
		deb(MST);
		se.cl();
		vis.reset();
	}
}

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