#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 2e5 + 5, Maxm = 5e5 + 5, LogN = 19;
static constexpr int64_t inf = 0x3f3f3f3f3f3f3f3f;
int n, m, fa[Maxn], lowbit[Maxn];
int fnd(int x) { return x == fa[x] ? x : fa[x] = fnd(fa[x]); }
vector<pair<int, int64_t>> g[Maxn];
int64_t ans[2], cur;
struct edge {
  int u, v, w;
  edge() = default;
  friend bool operator < (const edge &lhs, const edge &rhs) {
    return lhs.w < rhs.w;
  }
} e[Maxm];
bool has[Maxm];
int top[Maxn], par[Maxn], dep[Maxn], hson[Maxn], siz[Maxn], dfn[Maxn], idfn[Maxn], dn;
int64_t s[2][LogN][Maxn], a[2][Maxn], b[2][Maxn];
void dfs1(int u, int fa, int depth) {
  par[u] = fa, siz[u] = 1, dep[u] = depth; hson[u] = 0;
  for (const auto &[v, w]: g[u]) if (v != fa) {
    a[0][v] = (w % 2 == 1 ? -inf : w);
    a[1][v] = (w % 2 == 0 ? -inf : w);
    dfs1(v, u, depth + 1), siz[u] += siz[v];
    if (siz[v] > siz[hson[u]]) hson[u] = v;
  }
} // dfs
void dfs2(int u, int topu) {
  top[u] = topu;
  dfn[u] = ++dn; idfn[dn] = u;
  if (hson[u]) dfs2(hson[u], topu);
  for (const auto &[v, w]: g[u])
    if (v != par[u] && v != hson[u])
      dfs2(v, v);
} // dfs2
int64_t query(int k, int l, int r) {
  int j = lowbit[r - l + 1];
  return max(s[k][j][l], s[k][j][r - (1 << j) + 1]);
} // query
int64_t ask(int k, int u, int v) {
  int64_t ret = 0;
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]]) swap(u, v);
    ret = max(ret, query(k, dfn[top[v]], dfn[v]));
    v = par[top[v]];
  }
  if (dep[u] > dep[v]) swap(u, v);
  ret = max(ret, query(k, dfn[u], dfn[v]));
  return ret;
} // ask
int main(void) {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tests; cin >> tests;
  while (tests--) {
    cin >> n >> m;
    ans[0] = ans[1] = inf; cur = 0; dn = 0;
    for (int i = 1; i <= n; ++i) g[i].clear();
    for (int i = 1; i <= m; ++i) has[i] = false;
    for (int i = 2; i <= n; ++i) lowbit[i] = lowbit[i >> 1] + 1;
    for (int i = 1; i <= m; ++i)
      cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
      int u = e[i].u, v = e[i].v, w = e[i].w;
      int fu = fnd(u), fv = fnd(v);
      if (fu == fv) continue; has[i] = true;
      fa[fu] = fv;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
      cur += w;
    } ans[cur & 1] = cur;
    bool uncon = false;
    for (int i = 1; i <= n; ++i) if (fnd(i) != fnd(1)) uncon = true;
    if (uncon) { cout << "-1 -1\n"; continue; }
    dfs1(1, 0, 1), dfs2(1, 1);
    for (int k = 0; k < 2; ++k) {
      for (int i = 1; i <= n; ++i) s[k][0][i] = b[k][i] = a[k][idfn[i]];
      for (int j = 1; j < LogN; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
          s[k][j][i] = max(s[k][j - 1][i], s[k][j - 1][i + (1 << j - 1)]);
    }
    int64_t ruc = inf;
    for (int i = 1; i <= m; ++i) if (!has[i]) {
      int u = e[i].u, v = e[i].v, w = e[i].w;
      ruc = min(ruc, w - ask((w & 1) ^ 1, u, v));
    }
    ans[(cur & 1) ^ 1] = cur + ruc;
    cout << (ans[0] >= inf ? -1 : ans[0]) << ' ' << (ans[1] >= inf ? -1 : ans[1]) << endl;
  }
  return 0;
} // main