#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
#define fi first
#define se second

const int N = 200005;
pair<int, int> s[N][21];
int f[N][21], dep[N];
inline pair<int, int> getmax(pair<int, int> a, pair<int, int> b){
    return {max(a.fi, b.fi), max(a.se, b.se)};
}
inline void dfs(int u, int fa, vector<vector<pair<int, int> > > &g){
    dep[u] = dep[fa] + 1;
    for(int i = 1; i <= 20; i++){
        f[u][i] = f[f[u][i-1]][i-1];
        s[u][i] = getmax(s[u][i-1], s[f[u][i-1]][i-1]);
    }
    for(auto [v, w] : g[u]) if(v != fa){
        f[v][0] = u;
        s[v][0] = (w & 1) ? make_pair(w, 0) : make_pair(0, w);
        dfs(v, u, g);
    }
}

inline pair<int, int> query(int x, int y){
    pair<int, int> res = {0, 0};
    if(dep[x] > dep[y]) swap(x, y);
    for(int i = 20; ~i; i--) if(dep[f[x][i]] >= dep[y]){
        res = getmax(res, s[x][i]);
        x = f[x][i];
    }
    if(x == y) return res;
    for(int i = 20; ~i; i--) if(f[x][i] != f[y][i]){
        res = getmax(res, s[x][i]);
        res = getmax(res, s[y][i]);
        x = f[x][i], y = f[y][i];
    }
    return getmax(getmax(res, s[x][0]), s[y][0]);
}

inline void solve(){
    int n, m; vector<tuple<int, int, int> > edges;
    read(n), read(m);
    vector<vector<pair<int, int> > > g(n + 1);
    vector<int> fa(n + 1);
    for(int i = 1; i <= n; i++) fa[i] = i;
    ll sum = 0; int cnt = 0;

    auto unite = [&] (int x, int y, int z) -> void {
        auto ask = [&] (auto &ask, int x) -> int {
            return x == fa[x] ? x : 
                fa[x] = ask(ask, fa[x]);
        };
        int p = ask(ask, x), q = ask(ask, y);
        if(p == q) return;
        fa[p] = q, sum += z, cnt++;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    };

    for(int i = 1, x, y, z; i <= m; i++){
        read(x), read(y), read(z);
        edges.push_back({z, x, y});
    }

    sort(edges.begin(), edges.end());
    for(auto [z, x, y] : edges) unite(x, y, z);
    if(cnt < n - 1) return (void) (puts("-1 -1"));
    dfs(1, 0, g);

    ll sum2 = -1;

    for(auto [z, x, y] : edges){
        auto [w1, w0] = query(x, y);
        if(z % 2 == 1 && !w0) continue;
        if(z % 2 == 0 && !w1) continue;
        ll tmp = sum + z - ((z & 1) ? w0 : w1);
        if(sum2 == -1 || tmp < sum2) sum2 = tmp;
    }

    if(sum & 1) printf("%lld %lld\n", sum2, sum);
    else printf("%lld %lld\n", sum, sum2); 
}

int main(){
    int T; read(T);
    while(T--) solve();
}