#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200010;
const int M = 500010;
const int inf = 1e9+10;
const ll infl = 1e15;

int n, m, fa_union[N], use[M];
array<int,3> e[M];
vector<pair<int,int>> G[N];
int find(int u){ return fa_union[u]==u? u: fa_union[u] = find(fa_union[u]); }

int fa[N][20], maxe[N][20][2], dep[N];
void dfs(int u, int pre, int pre_w){
    fa[u][0] = pre;
    for(int i = 1; i < 20; i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    maxe[u][0][pre_w&1] = pre_w;
    maxe[u][0][pre_w&1^1] = -inf;
    dep[u] = dep[pre] + 1;
    for(int i = 1; i < 20; i++){
        maxe[u][i][0] = max(maxe[u][i-1][0], maxe[fa[u][i-1]][i-1][0]);
        maxe[u][i][1] = max(maxe[u][i-1][1], maxe[fa[u][i-1]][i-1][1]);
    }
    for(auto v: G[u]){
        if(v.first == pre) continue;
        dfs(v.first, u, v.second);
    }
    return;
}

int get_lca(int u, int v, array<int,2>& maxe_res){
    if(dep[u] > dep[v]) swap(u, v);
    maxe_res = {-inf, -inf};
    for(int i = 19; i >= 0; i--)
        if(dep[fa[v][i]] >= dep[u]){
            maxe_res[0] = max(maxe_res[0], maxe[v][i][0]);
            maxe_res[1] = max(maxe_res[1], maxe[v][i][1]);
            v = fa[v][i];
        }
    if(v == u)
        return u;
    for(int i = 19; i > 0; i--)
        if(fa[v][i] != fa[u][i]){
            maxe_res[0] = max(maxe_res[0], min(maxe[v][i][0], maxe[u][i][0]));
            maxe_res[1] = max(maxe_res[1], min(maxe[v][i][1], maxe[u][i][1]));
            u = fa[u][i], v = fa[v][i];
        }
    maxe_res[0] = max(maxe_res[0], max(maxe[v][0][0], maxe[u][0][0]));
    maxe_res[1] = max(maxe_res[1], max(maxe[v][0][1], maxe[u][0][1]));
    u = fa[u][0], v = fa[v][0];
    return u;
}

ll sum = 0, ans[2];
void solve(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        G[i].clear();
        fa_union[i] = i;
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
        use[i] = 0;
    }
    sort(e+1, e+m+1, [&](auto u, auto v){
        return u[2] < v[2];
    });
    sum = 0; ans[0] = ans[1] = infl;
    for(int i = 1; i <= m; i++){
        int fa1 = find(e[i][0]);
        int fa2 = find(e[i][1]);
        if(fa1 != fa2){
            // printf("choose %d\n", i);
            use[i] = 1;
            fa_union[fa1] = fa2;
            G[e[i][0]].push_back(make_pair(e[i][1], e[i][2]));
            G[e[i][1]].push_back(make_pair(e[i][0], e[i][2]));
            sum += e[i][2];
        }
    }
    for(int i = 1; i <= n; i++)
        if(find(i) != find(1)){
            printf("-1 -1\n");
            return;
        }
    ans[sum&1] = sum;
    for(int i = 0; i < 20; i++)
        maxe[0][i][0] = maxe[0][i][1] = -inf;
    dfs(1, 0, inf);
    for(int i = 1; i <= m; i++)
        if(!use[i]){
            array<int,2> t;
            int lca = get_lca(e[i][0], e[i][1], t);
            if(t[0] > -inf) ans[(sum+e[i][2]-t[0])&1] = min(ans[(sum+e[i][2]-t[0])&1], sum+e[i][2]-t[0]);
            if(t[1] > -inf) ans[(sum+e[i][2]-t[1])&1] = min(ans[(sum+e[i][2]-t[1])&1], sum+e[i][2]-t[1]);
            // printf("%d %d %d\n", i, t[0], t[1]);
        }
    printf("%lld %lld\n", ans[0]==infl?-1ll:ans[0], ans[1]==infl?-1ll:ans[1]);
    return;
}

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