#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 7;
const int M = 5e5 + 7;
int T , n , m ;


struct dsu{
	int fa[N];
	void init(){
		for(int i=1;i<=n;i++) fa[i] = i;
	}
	int find(int x){
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	void merge(int x,int y){
		x = find(x);
		y = find(y);
		if(x!=y){
			fa[x] = y;
		}
	}
};
int dep[N];
int topfa[N][22];
int topfw[2][N][22];
vector<int>gra[N];
struct edge{
	int u , v , w, tag;
}t[M];


void dfs(int x,int f){
	dep[x] = dep[f] + 1;
	for(int i=0;i<=1;i++)
	for(int j=1;j<=20;j++){
		topfa[x][j] = topfa[topfa[x][j-1]][j-1];
		topfw[i][x][j] = min(topfw[i][x][j-1],topfw[i][topfa[x][j-1]][j-1]); 
	}
	
	for(auto e:gra[x]){
		int v = t[e].v;
		if(v==f) continue;
		int w = t[e].w;
		topfa[v][0] = x;
		topfw[w&1][v][0] = w;
		dfs(v,x);
	}
}


int Getlca(int x,int y){
	if(dep[x] < dep[y]) swap(x,y);
	int cha = dep[x] - dep[y];
	for(int i=20;i>=0;i--){
		if(cha >= (1<<i)){
			cha -= (1<<i);
			x = topfa[x][i];
		}
	}
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(topfa[x][i] != topfa[y][i]){
			x = topfa[x][i];
			y = topfa[y][i];
		}
	}
	return topfa[x][0];
}


int Get_val(int x,int lca,int tag){
	int ans = 1e18;
	
	for(int i=20;i>=0;i--){
		if(dep[topfa[x][i]] >= dep[lca]){
			ans = min(ans,topfw[tag][x][i]);
			x = topfa[x][i];
		}
	}
	return ans;
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
*/
int ANS[2];
void kruskal(){
	ANS[0] = ANS[1] = 1e18;
	sort(t+1,t+m+1,[](edge a,edge b){
		return a.w < b.w;
	});
	dsu now ;
	now.init();int cnt = 0 ;
	int ans = 0 ;
	for(int i=1;i<=m;i++) {
		if(now.find(t[i].u) != now.find(t[i].v)){
			now.merge(t[i].u,t[i].v);
			gra[t[i].u].emplace_back(i);
			gra[t[i].v].emplace_back(i);
			cnt ++ ;
			t[i].tag = 1;
			ans += t[i].w;
		}
	}
	ANS[ans&1] = ans; 
	if(cnt != n-1 ){
		cout << -1 << " " << -1 << endl;
		return ;
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		if(t[i].tag) continue;
		int x = t[i].u;
		int y = t[i].v;
		int lca = Getlca(x,y);
		bool w = !(t[i].w&1);
		int z = min(Get_val(x,lca,w),Get_val(y,lca,w));
		if(z==1e18) continue;
		ANS[!(ans&1)] = min(ANS[!(ans&1)],ans + t[i].w - z);
	}
	if(ANS[0] == 1e18) cout << -1 << " ";
	else cout << ANS[0] << " ";
	if(ANS[1] == 1e18) cout << -1 <<endl;
	else cout << ANS[1] <<endl;
}


void clear(){
	ANS[0] = ANS[1] =  1e18;
	for(int i=1;i<=m;i++) t[i].tag = 0 ;
	for(int i=1;i<=n;i++) 
	{
		dep[i] = 0 ;
		gra[i].clear();
	}
	for(int i=0;i<=1;i++)
	for(int x=1;x<=n;x++)
	for(int j=0;j<=20;j++){
		topfa[x][j] = 0 ;
		topfw[i][x][j] =  1e18;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T-->0){
		cin >> n >> m ;
		clear();
		for(int i=1;i<=m;i++){
			cin >> t[i].u >> t[i].v >> t[i].w;
		}

		kruskal();
		
	}
    return 0;
}