# include <bits/stdc++.h>

using namespace std ;

int n , m ;
struct Edge
{
	int to , next , w ;
} g[1000005] ;
int fte[500005] , gsz ;
void addedge( int x , int y , int z )
{
	g[++ gsz] = ( Edge ) { y , fte[x] , z } ;
	fte[x] = gsz ;
}
int f[200005] ;
int get(int x )
{
	if ( f[x] == x ) return x ;
	return f[x] = get( f[x] ) ;
}
void merge( int x , int y )
{
	f[get( x )] = get( f[y] ) ;
}
typedef long long ll ;
const int INF = 1e9 +5 ;
int maxv[200005][21][2] , fa[200005][21] ;
vector < pair< int , pair< int , int > > > gr ;
int deap[200005] ;
void dfs1( int x , int father )
{
	deap[x] = deap[father] + 1 ;
	fa[x][0] = father ;
	for ( int j = 1 ; j <= 20 ; j++ )
	{
		fa[x][j] = fa[fa[x][j - 1]][j - 1] ;
		for ( int t = 0 ; t <= 1 ; t++ )
			maxv[x][j][t] = max( maxv[x][j - 1][t] , 
			maxv[fa[x][j - 1]][j - 1][t] ) ;
	}
	for ( int i = fte[x] ; i ; i = g[i].next )
	{
		int y = g[i].to ;
		if ( y == father ) continue ;
		maxv[y][0][g[i].w & 1] = g[i].w ;
		dfs1( y , x ) ;
	}
}
int query( int x , int y , int t )
{
	if (deap[x] < deap[y] ) swap( x , y ) ;
	int ans = 0 ;
	for ( int i = 20 ; i >= 0 ; i-- )
		if ( deap[fa[x][i]] >= deap[y] ) 
		{
			ans = max( ans , maxv[x][i][t] ) ;
			x = fa[x][i] ;
		}
	if ( x == y ) return ans ;
	for ( int i = 20 ; i >= 0 ; i-- )
		if ( fa[x][i] != fa[y][i] ) 
		{
			ans = max( ans , max( maxv[x][i][t] , maxv[y][i][t] ) ) ;
			x = fa[x][i] , y = fa[y][i] ;
		}
	ans = max( ans , max(maxv[x][0][t] , maxv[y][0][t] ) ) ;
	return ans ;
}
void solve()
{
	scanf("%d%d" , &n , &m) ;
	gr.clear() ;
	gsz = 0 ;
	for ( int i = 1 ; i <= n ; i++ ) fte[i] = 0 , f[i] = i ;
	for ( int i = 1 ; i <= n ; i++ )
	{
		maxv[i][0][0] = maxv[i][0][1] = 0 ;
	}
	for ( int i = 1 ; i <= m ; i++)
	{
		int x , y , z ;
		scanf("%d%d%d" , &x , &y , &z) ;
		gr.push_back( { z , { x , y } } ) ;
	}
	sort( gr.begin() , gr.end() ) ;
	int ss = 0 ;
	ll ans = 0 ;
	int tt = 0 ;
	for ( auto t : gr )
	{
		int x = t.second.first , y = t.second.second ;
		int z = t.first ;
//		printf("now:%d %d %d\n" , x , y , z) ;
		if ( get( x ) == get( y ) ) continue ;
		addedge( x , y , z ) , addedge( y , x , z ) ;
		merge( x , y ) ;
		ss ^= ( z & 1 ) ;
		ans += z ;
		tt++ ;
	}
	deap[1] = 0 ;
	dfs1( 1 , 1 ) ;
	ll ans2 = ans + INF ;
	for ( auto t : gr )
	{
		int x = t.second.first , y = t.second.second ;
		int z = t.first ;
		int nv = query( x , y , ( z & 1 ) ^ 1 ) ;
		if ( nv ) ans2 = min( ans2 , ans - nv + z ) ;
	}
	if ( tt != n - 1 ) puts("-1 -1") ;
	else
	{
		if ( ans2 == ans + INF ) ans2 = -1 ;
		if (! ans & 1 ) printf("%lld %lld\n" , ans , ans2) ;
		else printf("%lld %lld\n" , ans2 , ans) ;
	}
}

int main()
{
	int t ;
	scanf("%d" , &t) ;
	while ( t -- ) solve() ;
	return 0 ;
}