#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 5;
const int maxm = 5e5 + 5;
const int maxlog = 17;
int n, m, flag, pa[maxn], val[maxn], f[2][maxn][maxlog + 1], fa[maxn][maxlog + 1], dep[maxn];
bool vis[maxn];
ll ans[2];
vector<pair<int, int>> g[maxn];
struct edge {
    int u, v, w;
} e[maxm];
int find(int x) {
    return (pa[x] == x) ? x : (pa[x] = find(pa[x]));
}
void dfs_pre(int u, int from) {
    dep[u] = dep[from] + 1;
    if(u != 1) {
        int o = val[u] & 1;
        f[o][u][0] = val[u];
        f[o ^ 1][u][0] = 0;
        fa[u][0] = from;
        for(int i = 1; i <= maxlog; i++) {
            f[0][u][i] = max(f[0][u][i - 1], f[0][fa[u][i - 1]][i - 1]);
            f[1][u][i] = max(f[1][u][i - 1], f[1][fa[u][i - 1]][i - 1]);
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
        }
    }
    for(auto i : g[u]) {
        int v = i.first, w = i.second;
        if(v == from) {
            continue;
        }
        val[v] = w;
        dfs_pre(v, u);
    }
}
int LCA(int x, int y) {
    if(dep[y] > dep[x]) {
        swap(x, y);
    }
    for(int i = maxlog; i >= 0; i--) {
        if(dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
    }
    if(x == y) {
        return x;
    }
    for(int i = maxlog; i >= 0; i--) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e + 1, e + 1 + m, [&](const edge &x, const edge &y) {
        return x.w < y.w;
    });
    ans[0] = ans[1] = flag = -1;
    for(int i = 1; i <= n; i++) {
        pa[i] = i;
        vis[i] = 0;
        g[i].clear();
    }
    ll res = 0;
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        if(find(e[i].u) != find(e[i].v)) {
            res += e[i].w;
            pa[find(e[i].u)] = find(e[i].v);
            cnt++;
            vis[i] = 1;
        }
    }
    if(cnt < n - 1) {
        cout << -1 << ' ' << -1 << '\n';
        return;
    }
    flag = (res & 1) ^ 1;
    ans[flag ^ 1] = res;
    for(int i = 1; i <= m; i++) {
        if(vis[i]) {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
    }
    dfs_pre(1, 0);
    for(int i = 1; i <= m; i++) {
        if(vis[i]) {
            continue;
        }
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int lca = LCA(u, v), mx = 0, o = (w & 1) ^ 1;
        for(int i = maxlog; i >= 0; i--) {
            if(fa[u][i] && dep[fa[u][i]] >= dep[lca]) {
                mx = max(mx, f[o][u][i]);
                u = fa[u][i];
            }
            if(fa[v][i] && dep[fa[v][i]] >= dep[lca]) {
                mx = max(mx, f[o][v][i]);
                v = fa[v][i];
            }
        }
        if(mx > 0) {
            if(ans[flag] == -1) {
                ans[flag] = ans[flag ^ 1] - mx + w;
            }
            else {
                ans[flag] = min(ans[flag], ans[flag ^ 1] - mx + w);
            }
        }
    }
    cout << ans[0] << ' ' << ans[1] << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        work();
    }    
    return 0;
}