#include<bits/stdc++.h>
#define int long long
const int N = 4e5 + 10;
const int INF = 1e9 + 7;
#define pii pair<int,int>
using namespace std;
int n, m, tot = 0, dfn[N], depth[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[35][N], lg[N], ff[35][N][2];
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 piiquery(int l, int r){
	int k = lg[r - l + 1];
	// cout << r - l + 1 << endl;
	// cout << k << endl;
	// cout << ff[k][l][0] << " " << ff[k][r + 1 - (1 << k)][0] << endl;
	return 
	{
		max(ff[k][l][0], ff[k][r + 1 - (1 << k)][0]),
		max(ff[k][l][1], ff[k][r + 1 - (1 << k)][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 = 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, 1, -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;
		if(pot[y] < pos[x]) swap(x, y);
		// cout << pos[x] << " " << pot[y] << endl;
		auto[f, s] = piiquery(pos[x], pot[y]);
		// cout << f << " " << s << endl;
		int ss[2]; ss[0] = f, ss[1] = s;
		int xx = w & 1; xx ^= 1;
		if(ss[xx] == -1) continue;
		// cout << xx << endl;
		// cout <<  << endl;
		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();
}