#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

using namespace std;

const int nmax = 200001;

int p[nmax][22];
ll max_even[nmax][22];
ll max_odd[nmax][22];
int in[nmax], out[nmax];
int d[nmax];
int timer =0;
void dfs(int v, int e, vector <vector<pii>>&g) {
    in[v] = timer++;
    p[v][0] = e;
    for(int j = 1; j < 22; j++) {
        p[v][j] = p[p[v][j - 1]][j -1];
        int x = p[v][j - 1];
        max_even[v][j] = max(max_even[v][j - 1], max_even[x][j - 1]);
        max_odd[v][j] = max(max_odd[v][j - 1], max_odd[x][j - 1]);
    }
    for(auto [to, len] : g[v]) {
        if(to == e) continue;
        d[to] = d[v] + 1;
        if(len % 2 == 0)
            max_even[to][0] = len;
        else max_odd[to][0] = len;
        dfs(to, v, g);
    }
    out[v] = timer++;
}

bool is_anc(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v) {
    if(is_anc(u, v)) return u;
    if(is_anc(v, u)) return v;
    for(int j = 21; j >= 0; j--) {
        if(!is_anc(p[v][j - 1], u)) v =p[v][j - 1];
    }
    return p[v][0];
}

ll get_max_even(int v, int d) {
    ll ans = -1e18;
    while(d > 0) {
        int x = 31 - __builtin_clz(d);
        ans = max(ans, max_even[v][x]);
        v = p[v][x];
        d -= (1 << x);
    }
    return ans;
}

ll get_max_odd(int v, int d) {
    ll ans = -1e18;
    while(d > 0) {
        int x = 31 - __builtin_clz(d);
        ans = max(ans, max_odd[v][x]);
        v = p[v][x];
        d -= (1 << x);
    }
    return ans;
}

class DSU {
public :
    void union_sets(int u, int v) {
        u = find(u); v = find(v);
		if(u == v) {
			return;
		}
		if(sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
    }
    int find(int x) {
     return p[x] == x ? x : p[x] = find(p[x]);
    }
    DSU(int n) {
        p.resize(n + 1);
        for(int i = 1; i <= n; i++) p[i] = i;
        sz.resize(n + 1, 1);
    }

    vector <int> p, sz;
};

void reset(int n) {
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 22; j++) {
            max_even[i][j] = -1e18;
            max_odd[i][j] = -1e18;
            p[i][j] = 0;
            in[i] = out[i] = 0;
            d[i] = 0;
        }
    }
    timer = 0;
}

void solve() {
    int n, m; cin >> n >> m;
    reset(n);
    vector <pair<int, pii>>edges;
    for(int i= 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        int l; cin >> l;
        edges.pb({l, {u, v}});
    }
    sort(edges.begin(), edges.end());
    DSU ds(n);
    vector <vector <pii>>g(n + 1);
    ll tot = 0;
    for(auto x : edges) {
        ll len = x.f;
        int u = x.s.f, v = x.s.s;
        if(ds.find(u) != ds.find(v)) {
            g[u].pb({v, len});
            g[v].pb({u, len});
            ds.union_sets(u, v);
            tot += len;
        }
    }
    if(ds.sz[ds.find(1)] != n) {
        cout << -1 << ' ' << -1 << '\n';
        return;
    }
    dfs(1, 1, g);
    ll ans = 1e18;
    for(auto x : edges) {
        ll len = x.f;
        int u = x.s.f;
        int v = x.s.s;
        int l = lca(u, v);
        ll even = get_max_even(u, d[u] - d[l]);
        ll odd = get_max_odd(v, d[v] - d[l]);
        if(len % 2 == 0) {
            ans = min(ans, len - odd);
        }
        else ans = min(ans, len - even);
    }
    ll res[2];
    int x = tot % 2;
    
    res[x] = tot, res[x ^ 1] = tot + ans;
    for(int i = 0; i < 2; i++){
        if(res[i] > (ll)1e18) res[i] = -1;
        cout << res[i] << ' ';
    }
    cout << '\n';
}

int main() {
    int test; cin>> test;

    while(test--) {
    solve();
    }
    return 0;
}