#include <bits/stdc++.h>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
#define SZ(x) ((int)(x).size())
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
using ll = long long;
const int inf = 0x3f3f3f3f3f3f3f3fLL;

#define MULTI_TEST

class DSU {
public:
    vector<int> fa, sz;
    DSU(int n) : fa(n + 1), sz(n + 1) {
        iota(fa.begin(), fa.end(), 0);
        fill(sz.begin() + 1, sz.end(), 1);
    }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    void merge(int a, int b) {
        int x = find(a), y = find(b); 
        if(x == y) return ;
        fa[y] = x;
        sz[x] += sz[y];
    }
};

void solve() {
    int n, m; cin >> n >> m;
    vector<array<int, 3>> edg(m);
    vector<int> used(m);
    vector adj(n + 1, vector<int> ());
    for(int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edg[i] = {w, u, v};
    }
    ranges::sort(edg);
    DSU dsu(n);
    int sum = 0;
    for(int i = 0; i < SZ(edg); i++) {
        auto [w, u, v] = edg[i];
        int f1 = dsu.find(u), f2 = dsu.find(v);
        
        if(f1 == f2) continue;
        dsu.merge(f1, f2);
        used[i] = 1;
        sum += w;

        // adj[f1].push_back(f2);
        // adj[f1].push_back(f1);
    }

    if(dsu.sz[dsu.find(1)] != n) {
        cout << "-1 -1\n";
        return ;
    }

    array<int, 2> ans{sum, inf};
    array<int, 2> minx{inf, inf};

    for(int i = 0; i < m; i++) {
        auto [w, u, v] = edg[i];
        if(!used[i]) {
            minx[w % 2] = min(minx[w % 2], w);
        }
    }

    for(int i = 0; i < m; i++) {
        auto [w, u, v] = edg[i];
        if(used[i]) {
            ans[1] = min(ans[1], sum - w + minx[(w % 2) ^ 1]);
        }
    }

    if(ans[1] == inf) {
        if(ans[0] % 2 == 0) cout << ans[0] << " -1\n";
        else cout << "-1 " << ans[0] << "\n";
        return ;
    }

    if(ans[0] % 2 != 0) {
        swap(ans[0], ans[1]);
    } 
    cout << ans[0] << " " << ans[1] << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
#ifdef MULTI_TEST
    int T; cin >> T;
#else
    int T = 1;
#endif
    while(T--) solve();
    return 0;
}

/*

3
2 1
1 2 5

3 1
1 3 1

4 4
1 2 1
1 3 1
1 4 1
2 4 2

*/