#include<bits/stdc++.h>
// #define int long long
const int N = 2e5 + 10;
const int INF = 1e9 + 7;
#define ll long long
#define pii pair<int,int>
using namespace std;
int n, m, tot = 0, dfn[N], dep[N], pos[N], pot[N], len[N];
vector<pii> G[N];
struct Edge{
	int u, v, w;
};
int fa[N];
//void dfs(int cur, int dep, int ww){
//        dfn[++tot] = cur;
//        len[tot] = ww;
//        depth[tot] = dep;
//        pos[cur] = tot;
//        pot[cur] = tot;
//        for(auto [y, w]: G[cur]){
//                if(!pos[y]){
//                        dfs(y, dep + 1, w);
//                        dfn[++tot] = cur, depth[tot] = dep;
//                        pot[cur] = max(pot[cur], tot);
//                }
//        }
//}
int rev[N][20], ff[N][20][2];
void dfs (int u, int fa, int w) {
	dep[u] = dep[fa] + 1;
	rev[u][0] = fa;
	if(w == -1){
		ff[u][0][0] = -INF;
		ff[u][0][1] = -INF;
	}else{
		ff[u][0][w & 1] = w;
		ff[u][0][(w & 1) ^ 1] = -INF; 
	}
	for (int i = 1; i <= 18; i ++ ) {
		rev[u][i] = rev[rev[u][i - 1]][i - 1];
	    ff[u][i][0] = max (ff[u][i - 1][0], ff[rev[u][i - 1]][i - 1][0]);
		ff[u][i][1] = max (ff[u][i - 1][1], ff[rev[u][i - 1]][i - 1][1]);
	}
	for(auto[v, w]: G[u]){
		if(v == fa) continue;
		dfs(v, u, w);
	}
}
pii LCA (int x, int y) {
	vector<int> ans(2);
	ans[0] = ans[1] = -INF;
	if (dep[x] < dep[y]) swap (x, y);
	for (int i = 18; i >= 0; i -- ) {
		if (dep[rev[x][i]] >= dep[y]){
			ans[0] = max(ans[0], ff[x][i][0]);
			ans[1] = max(ans[1], ff[x][i][1]);
			x = rev[x][i];
		}
	}
	if (x == y) return {ans[0], ans[1]};
	for (int i = 18; i >= 0; i -- ) {
		if (rev[x][i] != rev[y][i]) {
			ans[0] = max(ans[0], max(ff[x][i][0], ff[y][i][0]));
			ans[1] = max(ans[1], max(ff[x][i][1], ff[y][i][1]));
			x = rev[x][i];
			y = rev[y][i];
		}
	}
	ans[0] = max(ans[0], max(ff[x][0][0], ff[y][0][0]));
	ans[1] = max(ans[1], max(ff[x][0][1], ff[y][0][1]));
	return {ans[0], ans[1]};
}
int find(int x){
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
// int vis[N];
void clear(){
	// lg[0] = -1;
	tot = 0;
	for(int i = 1; i <= n; ++ i) G[i].clear(), fa[i] = i;
	for(int i = 1; i <= 2 * n; ++ i) len[i] = -1;
	// for(int i = 1; i <= 2 * n; ++ i) lg[i] = ((i & (i - 1)) == 0) ? lg[i - 1] + 1 : lg[i - 1];
	// for(int i = 0; i <= m; ++ i) vis[i] = 0;
}
void solve(){
	cin >> n >> m;
	clear();
	vector<int> flag(m + 1);
	vector<Edge> E;
	for(int i = 1; i <= m; ++ i){
		int x, y, w;
		cin >> x >> y >> w;
		E.push_back({x, y, w});
	}
	sort(E.begin(), E.end(), [&](Edge a, Edge b){
		return a.w < b.w;
	});
	int cnt = 0;
	ll tt = 0;
	vector<ll> ans(2);
	ans[0] = ans[1] = 1e15;
	for(int i = 0; i < E.size(); ++ i){
		int x = E[i].u, y = E[i].v, w = E[i].w;
		if(cnt == n - 1) break;
		int xx = find(x), yy = find(y);
		if(xx != yy){
			G[x].push_back({y, w});
			G[y].push_back({x, w});
			cnt ++;
			fa[x] = yy;
			flag[i] = 1;
			tt += w;
		} 
	}	
	dfs(1, 0, -1);
	// for(int i = 1; i <= tot; ++ i) cout << dfn[i] << " " << len[i] << endl;
	// init();
	// for(int i = 1; i <= tot; ++ i) cout << lg[i] << endl;
	if(cnt != n - 1){
		cout << "-1 -1" << endl;
		return;
	}
	ll xxx = tt & 1;
	ans[xxx] = tt;
	for(int i = 0; i < E.size(); ++ i){
		if(flag[i]) continue;
		int x = E[i].u, y = E[i].v, w = E[i].w;
		auto[f, s] = LCA(x, y);
		int ss[2]; ss[0] = f, ss[1] = s;
		int xx = w & 1; xx ^= 1;
		if(ss[xx] <= -1) continue;
		ans[xxx ^ 1] = min(ans[xxx ^ 1], ans[xxx] - ss[xx] + w);
	}
	cout << (ans[0] == INF? -1 : ans[0]);
	cout << " " << (ans[1] == INF? -1 : ans[1]) << endl; 
}
signed main(){
	ios::sync_with_stdio(0);
	int T; cin >> T;
	while(T--) solve();
}