#include<bits/stdc++.h>
#define int long long
const int N = 4e5 + 10;
const int INF = 1e14 + 7;
#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 st[35][N], rev[N][35], lg[N], ff[N][35][2];
inline 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{
		int tt = w & 1;
		ff[u][0][tt] = w;
		ff[u][0][tt ^ 1] = -INF; 
	}
	for (int i = 1; i <= 20; 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]);
//		h[u][i] = max (h[u][i - 1], h[f[u][i - 1]][i - 1]);
		ff[u][i][1] = max (ff[u][i - 1][1], ff[rev[u][i - 1]][i - 1][1]);
	}
//	for (int i = head[u]; i; i = edge[i].next ) {
//		int v = edge[i].to, w = edge[i].w;
//		if (v == fa) continue;
//		dfs (v, u, w);
//	}
	for(auto[v, w]: G[u]){
		if(v == fa) continue;
		dfs(v, u, w);
	}
}
//void init(){
//        for(int i = 1; i <= tot; ++ i) st[0][i] = depth[i], rev[0][i] = dfn[i],  lg[i] = ((i & (i - 1)) == 0) ? lg[i - 1] + 1 : lg[i - 1];
//        for(int i = 1; i <= tot; ++ i){
//        	if(len[i] == -1) ff[0][i][0] = -1, ff[0][i][1] = -1;
//        	else {
//        		int x = len[i] & 1;
//        		ff[0][i][x ^ 1] = -1;
//        		ff[0][i][x] = len[i];
//        	}
//        }
//        for(int i = 1; i <= lg[tot]; ++ i)
//                for(int j = 1; j + (1 << i) - 1 <= tot; ++ j)
//                        if(st[i - 1][j] < st[i - 1][j + (1 << (i - 1))]){
//                            	st[i][j] = st[i - 1][j], rev[i][j] = rev[i - 1][j];
//                            	ff[i][j][0] = ff[i - 1][j][0];
//                            	ff[i][j][1] = ff[i - 1][j][1];
//                            }
//                        else 
//                        {
//                        	st[i][j] = st[i - 1][j + (1 << (i - 1))], rev[i][j] = rev[i - 1][j + (1 << (i - 1))];
//                        	ff[i][j][0] = max(ff[i - 1][j][0], ff[i - 1][j + (1 << (i - 1))][0]);
//                        	ff[i][j][1] = max(ff[i - 1][j][1], ff[i - 1][j + (1 << (i - 1))][1]);
//                        }
//}
//int query(int l, int r){
//        int k = lg[r - l + 1];
//        return st[k][l] < st[k][r + 1 - (1 << k)] ? rev[k][l]: rev[k][r + 1 - (1 << k)];
//}
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 = 20; 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 = 20; 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, tt = 0;
	vector<int> ans(2);
	ans[0] = ans[1] = INF;
	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;
	}
	int 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();
}