#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define MAXN 100010
#define int ll

namespace BCJ
{
    int fa[MAXN];
    void init(int n)
    {
        for (int i = 1; i <= n; i++)
        {
            fa[i] = i;
        }
    }
    int find(int x)
    {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void unity(int x, int y)
    {
        fa[find(x)] = find(y);
    }
};

void solve()
{
    int n, m;
    cin >> n >> m;
    int logn = log2(n) + 3;
    vector<pair<int, pair<int, int>>> eds(m);
    vector<bool> tag(m);
    for (int i = 0; i < m; i++)
    {
        cin >> eds[i].second.first >> eds[i].second.second >> eds[i].first;
    }
    vector<vector<pair<int, int>>> adj(n + 1);
    BCJ::init(n);
    sort(eds.begin(), eds.end());
    int ans = 0;
    int toted = 0;
    for (int i = 0; i < m; i++)
    {
        auto &[w, uv] = eds[i];
        auto &[u, v] = uv;
        if(BCJ::find(u) != BCJ::find(v))
        {
            // cerr << "u=" << u << " v=" << v << endl;
            ans += w;
            BCJ::unity(u, v);
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
            tag[i] = 1;
            toted++;
        }
    }
    if(toted != n - 1)
    {
        cout << -1 << " " << -1 << '\n';
        return;
    }

    vector<vector<int>> fa(n + 1, vector<int>(logn, 0));
    vector<vector<array<int, 2>>> mxnum(n + 1, vector<array<int, 2>>(logn, {0, 0}));
    vector<int> deep(n + 1);
    auto dfs = [&](auto self, int cur, int father, int lstval) -> void
    {
        fa[cur][0] = father;
        mxnum[cur][0][lstval % 2] = lstval;
        for (int i = 1; i < logn; i++)
        {
            fa[cur][i] = fa[fa[cur][i - 1]][i - 1];
            mxnum[cur][i][0] = max(mxnum[cur][i - 1][0], mxnum[fa[cur][i - 1]][i - 1][0]);
            mxnum[cur][i][1] = max(mxnum[cur][i - 1][1], mxnum[fa[cur][i - 1]][i - 1][1]);
        }
        for (auto &[to, w] : adj[cur])
        {
            if(to == father)
                continue;
            self(self, to, cur, w);
        }
    };
    dfs(dfs, 1, 0, 0);

    auto getmxnum = [&](int x, int y) -> array<int, 2>
    {
        if(deep[x] > deep[y])
            swap(x, y);
        array<int, 2> ans = {0, 0};
        int temp = deep[y] - deep[x];
        for (int i = 0; i < logn; i++)
        {
            if(temp >> i & 1)
            {
                ans = max(ans, mxnum[y][i]);
                y = fa[y][i];
            }
        }
        if(x == y)
            return ans;
        for (int i = logn - 1; i >= 0; i--)
        {
            if(fa[x][i] != fa[y][i])
            {
                ans = max(ans, mxnum[x][i]);
                ans = max(ans, mxnum[y][i]);
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        ans = max(ans, mxnum[x][0]);
        ans = max(ans, mxnum[y][0]);
        return ans;
    };

    int newans = ans;
    for (int i = 0; i < m; i++)
    {
        if(tag[i])
            continue;
        auto &[w, uv] = eds[i];
        auto &[u, v] = uv;
        auto newmx = getmxnum(u, v);
        newans = max(newans, ans + w - newmx[!(w % 2)]);
    }
    if(newans == ans)
    {
        if(ans % 2 == 0)
            cout << ans << " " << -1 << '\n';
        else
            cout << -1 << " " << ans << '\n';
    }
    else
    {
        if(ans % 2 == 0)
            cout << ans << " " << newans << '\n';
        else
            cout << newans << " " << ans << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}