#include <bits/stdc++.h>
#define NOSYNC ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define INF INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 200005;
const int M = 500005;
const int S = 21;
// -------------- Templates Above -------------------------
int n, m;
struct node {
	int v, w;
};
struct edge {
	int u, v, w, id;
	bool operator < (const edge &o) const {
		return w < o.w;
	}
};
edge e[M];
vector<node> G[N], g[N];
int ans[2];
// -----------------------------------------------
int dad[N]; int choose[M]; // 记录选择的边
int getfa(int x) {
	if(dad[x] == x) return x;
	return dad[x] = getfa(dad[x]);
}
bool ask(int x, int y) {
	int fx = getfa(x);
	int fy = getfa(y);
	if(fx == fy) return 1;
	return 0;
}
void merge(int x, int y) {
	if(!ask(x, y)) dad[getfa(x)] = getfa(y);
}
int kruskal() {
	for(int i = 1; i <= n; i ++) dad[i] = i;
	int cnt = 0; int ans = 0;
	sort(e+1, e+1+m);
	for(int i = 1; i <= m; i ++) {
		if(!ask(e[i].u, e[i].v)) {
			ans += e[i].w;
			cnt ++;
			merge(e[i].u, e[i].v);
			choose[e[i].id] = 1;
		}
		if(cnt == n-1) break;
	}
	if(cnt < n-1) return -1;
	return ans;
}
// -----------------------------------------------
int hson[N], dep[N], siz[N], fa[N];
int top[N], id[N], rnk[N], dfncnt;
int pval[N];
int st[2][N][22];
int logn[N];

void build() {
	for(int i = 1; i <= n; i ++) {
		int val = pval[rnk[i]];
		if(val & 1) {
			st[1][i][0] = val;
			st[0][i][0] = INF;	
		}
		else {
			st[0][i][0] = val;
			st[1][i][0] = INF;	
		}
	}
	for(int j = 1; j <= S; j ++) {
		for(int i = 1; i + (1 << j) - 1 <= n; i ++) {
			st[0][i][j] = max(st[0][i][j], st[0][i + (1 << (j-1))][j-1]);
			st[1][i][j] = max(st[1][i][j], st[1][i + (1 << (j-1))][j-1]);
		} 
	}
}
int rangeQmax(int which, int l, int r) {
	int s = logn[r - l + 1];
	return max(st[which][l][s], st[which][r - (1 << s) + 1][s]);
}

void dfs1(int x) {
	hson[x] = -1;
	siz[x] = 1;
	for(auto [y, w] : g[x]) {
		if(dep[y]) continue;
		fa[y] = x;
		dep[y] = dep[x] + 1;
		pval[y] = w;
		dfs1(y);
		siz[x] += siz[y];
		if(hson[x] == -1 || siz[y] > siz[hson[x]]) hson[x] = y;
	}
}
void dfs2(int x, int t) {
	top[x] = t;
	id[x] = ++dfncnt;
	rnk[dfncnt] = x;
	if(hson[x] != -1) dfs2(hson[x], t);
	for(auto [y, w] : g[x]) {
		if(y != fa[x] && y != hson[x]) dfs2(y, y);
 	}
}
int pathQmax(int which, int x, int y) {
	int res = -1;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		res = max(res, rangeQmax(which, id[top[x]], id[x]));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	if(x != y) res = max(res, rangeQmax(which, id[x]+1, id[y]));
	return res;
}
// -----------------------------------------------
void clear() {
	for(int i = 1; i <= n; i ++) {
		st[0][i][0] = 0;
		st[1][i][0] = 0;
	}
	for(int j = 1; j <= S; j ++) {
		for(int i = 1; i + (1 << j) - 1 <= n; i ++) {
			st[0][i][j] = 0;
			st[1][i][j] = 0;
		} 
	}
	for(int i = 1; i <= m; i ++) {
		e[i] = {0, 0, 0, 0};
	}
	for(int i = 1; i <= n; i ++) {
		g[i].clear();
	}
	for(int i = 1; i <= n; i ++) {
		hson[i] = siz[i] = dep[i] = fa[i] = 0;
		top[i] = id[i] = rnk[i] = 0; dfncnt = 0;
		pval[i] = 0;
	}
	for(int i = 1; i <= n; i ++) {
		dad[i] = 0;
	}
	for(int i = 1; i <= m; i ++) {
		choose[i] = 0;
	}
	ans[0] = ans[1] = 0;
}

void solve() {
	cin >> n >> m;
	for(int i = 1; i <= m; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[i] = {u, v, w, i};
		// G[u].push_back({v, w});
	}
	int res = kruskal(); 
	
	if(res == -1) {
		cout << -1 << " " << -1 << endl;
		clear();
		return;
	}
	
	
	ans[res&1] = res; // 求出其中一个答案
	ans[(res&1)^1] = INF;
	for(int i = 1; i <= m; i ++) {
		if(choose[i]) {
			auto [u, v, w, id] = e[i];
			g[u].push_back({v, w});
			g[v].push_back({u, w});
		}
	}
	dep[1] = 1;
	dfs1(1);
	dfs2(1, 1);
	build();
	for(int i = 1; i <= m; i ++) {
		if(choose[i]) continue;
		auto [u, v, w, id] = e[i];
		int which;
		if(w & 1) which = 0;
		else which = 1;
		// --------------------
		int mx = pathQmax(which, u, v);
		if(mx == INF) continue;
		ans[(res&1)^1] = min(ans[(res&1)^1], res - mx + w);
	}
	for(int i = 0; i <= 1; i ++) {
		if(ans[i] == INF) cout << -1 << " ";
		else cout << ans[i] << " ";
	}
	cout << endl;
	clear();
}
// -----------------------------------------------
signed main() {
	NOSYNC;
	logn[1] = 0;
	logn[2] = 1;
	for(int i = 3; i < N; i ++) {
		logn[i] = logn[i/2] + 1;
	}
	int t; cin >> t;
	for(int i = 1; i <= t; i ++) {
		// cout << "Case #" << i << ":" << endl;
		solve();
	}
	return 0;
}