#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int N = 2e5 + 7;
const int M = 5e5 + 7;
const int INF = 2000000000000000000ll;
int n = 0, m = 0;
struct Line {
    int id, u, v, w;
} e[M];

bool cmp(Line a, Line b) {
    return a.w < b.w;
}

int dad[N] = {0};
int ans[2];

vector<pair<int, int>> G[N];
int fa[N], depth[N] = {0}, heavy[N];
int siz[N], pt[N];
int rnk[N], top[N];
int cnt = 0, dfn[N];
int Logn[N];
int maxn[2][N][22];

void clear() {
    for (int i = 1; i <= m; i++) {
        e[i] = {0, 0, 0, 0};
    }
    ans[0] = ans[1] = 0;
    cnt = 0;
    for (int i = 1; i <= n; i++) {
        dad[i] = 0;
        G[i].clear();
        fa[i] = depth[i] = heavy[i] = 0;
        siz[i] = pt[i] = 0;
        rnk[i] = top[i] = 0;
        dfn[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        maxn[0][i][0] = 0;
        maxn[1][i][0] = 0;
    }

    for (int j = 1; j <= 21; j++) {
        for (int i = 1; i <= n; i++) {
            if (i + (1 << j) - 1 > n)break;
            maxn[0][i][j] = 0;
            maxn[1][i][j] = 0;
        }
    }
}

void reset() {
    for (int i = 1; i <= n; i++) {
        dad[i] = i;
    }
}

int find(int x) {
    if (dad[x] == x)return x;
    return dad[x] = find(dad[x]);
}

void merge(int a, int b) {
    dad[find(a)] = find(b);
}

void Dfs1(int u, int from) {
    siz[u] = 1;
    fa[u] = from;
    depth[u] = depth[from] + 1;
    for (auto [to, w]: G[u]) {
        if (to == from)continue;
        Dfs1(to, u);
        siz[u] += siz[to];
        pt[to] = w;
    }
    int big = 0;
    for (auto [to, w]: G[u]) {
        if (to == from)continue;
        if (siz[to] >= big) {
            big = siz[to];
            heavy[u] = to;
        }
    }
}

void Dfs2(int u) {
    if (!u)return;
    dfn[u] = ++cnt;
    rnk[cnt] = u;

    if (heavy[fa[u]] == u)top[u] = top[fa[u]];
    else top[u] = u; //判断u是否为新的重链头

    Dfs2(heavy[u]);

    for (auto [to, w]: G[u]) {
        if (to == fa[u] || to == heavy[u])continue;
        Dfs2(to);
    }
}

void BuildST() {
    for (int i = 1; i <= n; i++) {
        int val = pt[rnk[i]];
        maxn[val & 1][i][0] = val;
        maxn[1 - (val & 1)][i][0] = 0;
    }

    for (int j = 1; j <= 21; j++) {
        for (int i = 1; i <= n; i++) {
            if (i + (1 << j) - 1 > n)break;
            maxn[0][i][j] = max(maxn[0][i][j - 1], maxn[0][i + (1 << (j - 1))][j - 1]);
            maxn[1][i][j] = max(maxn[1][i][j - 1], maxn[1][i + (1 << (j - 1))][j - 1]);
        }
    }
}

int QueryST(int type, int l, int r) {
    if (l > r)swap(l, r);
    int s = Logn[r - l + 1];
    return max(maxn[type][l][s], maxn[type][r - (1 << s) + 1][s]);
}

int QueryPath(int type, int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]])swap(u, v);
        res = max(res, QueryST(type, dfn[u], dfn[top[u]]));
        u = fa[top[u]];
    }
    if (depth[u] > depth[v])swap(u, v);
    if (u != v)res = max(res, QueryST(type, dfn[v], dfn[u]));
    return res;
}

void solve() {
    clear();
    cin >> n >> m;
    reset();
    for (int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].id = 0;
    }

    sort(e + 1, e + 1 + m, cmp);
    int res1 = 0;
    int line_cnt = 0;
    for (int i = 1; i <= m; i++) {
        int u = e[i].u, v = e[i].v;
        if (find(u) == find(v))continue;
        res1 += e[i].w;
        e[i].id = 1;
        merge(u, v);
        line_cnt++;
        if(line_cnt == n-1) break;
    }

    if (line_cnt != n - 1) {
        cout << -1 << " " << -1 << endl;
        return;
    }

    ans[res1 & 1] = res1;
    ans[1 - (res1 & 1)] = INF;
    int ind = 1 - (res1 & 1);
    for (int i = 1; i <= m; i++) {
        if (!e[i].id)continue;
        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);
    }

    Dfs1(1, 0);
    Dfs2(1);
    BuildST();

    for (int i = 1; i <= m; i++) {
        if (e[i].id)continue;
        int u = e[i].u, v = e[i].v, w = e[i].w;
        int res = QueryPath(1 - (w & 1), u, v);
        if (res == 0)continue;
        ans[ind] = min(ans[ind], res1 - res + w);
    }

    if (ans[ind] == INF) {
        ans[ind] = -1;
    }
    cout << ans[0] << " " << ans[1] << endl;
}

void pre() {
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < N; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}

signed main() {
    // freopen("D:\\Development_Software\\CLion\\CLionProjects\\Test\\in", "r", stdin);
    pre();
    int T = 1;
    cin >> T;
    while (T--) solve();
}