#include <bits/stdc++.h>
#define xs(a) cout<<setiosflags(ios::fixed)<<setprecision(a);
#define endl '\n'
using namespace std;
using ll = long long;
const int N=1e6+5;
#define int long long

vector<array<int,2>>g[N];

int fa[N];
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]); 
}
int st[N][25][2];
int f[N][25], dep[N];
void dfs(int u, int par){
    dep[u] = dep[par] + 1;
    for(int i=1; i<=20; i++){
        f[u][i] = f[f[u][i-1]][i-1];
        for(int k=0; k<2; k++){
            st[u][i][k] = max(st[u][i-1][k], st[f[u][i-1]][i-1][k]);
        }
    }
    for(auto [v, w]: g[u]) if(v != par){
        st[v][0][w%2] = w; 
        dfs(v, u);
    }
}

int lca(int u, int v, int k){
    if(dep[u] < dep[v])swap(u, v);
    int ans = -1;
    for(int i=20; i>=0; i--){
        if(dep[f[u][i]] <= dep[v]){
            ans = max(ans, st[u][i][k]);
            u = f[u][i];
        }
    }
    if(u == v)return ans;
    for(int i=20; i>=0; i--){
        if(f[u][i] == f[v][i]) continue;
        ans = max({ans, st[u][i][k], st[v][i][k]});
        u = f[u][i], v = f[v][i];
    }
    ans = max({ans, st[u][0][k], st[v][0][k]});
    
    return ans;
}

void solve(){
    int n, m; cin >> n >> m;
    for(int i=1; i<=n; i++) {
        g[i].clear();
        fa[i] = i;
        for(int j=0; j<=20; j++) st[i][j][0] = st[i][j][1] = 0;
    }
    vector<array<int,3>>edg;
    int ans = 0;
    for(int i=1; i<=m; i++){
        int u, v, w; cin >> u >> v >> w;
        edg.push_back({w, u, v});
    }
    sort(edg.begin(), edg.end());
    vector<int>vis(n+5);
    int fk = 0;
    for(int i=0; i<edg.size(); i++){
        auto [w, u, v] = edg[i];
        int fu = find(u), fv = find(v);
        if(fu == fv)continue;
        ans += w;
        fk++;
        vis[i] = 1;
        fa[fu] = fv;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    if(fk != n-1){
        cout << "-1 -1"<<endl;
        return ;
    }
    dfs(1, 0);
    int res = 1e18;
    for(int i=0; i<edg.size(); i++)if(!vis[i]){
        auto [w, u, v] = edg[i];
        int x = lca(u, v, 1 - (w&1));
        if(x == -1)continue;
        res = min(res, ans - x + w);
    }
    if(res == 1e18)res = -1;
    if(ans%2) cout << res << ' ' << ans << endl;
    else cout << ans << ' ' << res << endl;

}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
    int T; cin >> T;
    while(T--)solve();


	return 0;
}