#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10,
          M = 500'000 + 10,
          MAXEDGE = 1'000'000'001;
const long long MAX = 1'000'000'000'000'000;

int n, m;
struct Edge { 
  int u, v, w;
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.u >> rhs.v >> rhs.w;
  }
} edge[M];
vector<pair<int, int>> ad[N];

int id[N];
int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
void add(int u, int v) { 
  u = root(u); v = root(v);
  if (u == v) return;
  if (id[u] > id[v]) swap(u, v);
  id[u] += id[v];
  id[v] = u;
}

int f[N][19], g[2][N][19], st[N], ed[N], it;
void dfs(int u, int p = -1) { 
  st[u] = ++it;
  
  for (int i = 1; i <= 18; ++i) { 
    f[u][i] = f[f[u][i - 1]][i - 1];
    for (int type = 0; type < 2; ++type) 
      g[type][u][i] = min(g[type][u][i - 1], g[type][f[u][i - 1]][i - 1]);
  }

  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    f[v][0] = u;
    g[w & 1][v][0] = w;
    g[!(w & 1)][v][0] = MAXEDGE;
    dfs(v, u);
  }

  ed[u] = it;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) { 
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;

  for (int i = 18; i >= 0; --i) 
    if (!anc(f[u][i], v)) u = f[u][i];

  return f[u][0];
}
int get(int u, int v, int type) { 
  int l = lca(u, v);
  int ret = MAXEDGE;
  
  for (int node = 0; node < 2; ++node) {
    for (int i = 18; i >= 0; --i) { 
      if (anc(f[u][i], l)) continue;
      ret = min(ret, g[type][u][i]);
      u = f[u][i];
    }
    if (u != l) ret = min(ret, g[type][u][0]);
    swap(u, v);
  }

  return ret;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int test; cin >> test;
  while (test--) { 
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> edge[i];

    sort(edge + 1, edge + m + 1, [&](const auto& a, const auto& b) { 
      return a.w < b.w;
    });
    
    memset(id, -1, (n + 1) * sizeof(int));
    long long total = 0;
    for (int i = 1; i <= m; ++i) { 
      const auto& [u, v, w] = edge[i];
      if (root(u) == root(v)) continue;
      add(u, v);
      ad[u].push_back({v, w});
      ad[v].push_back({u, w});
      total += w;
    }
    
    { //check connected
      int cnt = 0;
      for (int i = 1; i <= n; ++i) cnt += id[i] < 0;
      if (cnt > 1) { cout << -1 << " " << -1 << "\n"; continue; }
    }
    
    dfs(f[1][0] = 1);
    vector<long long> cost(2, 1'000'000'000'000'000);
    for (int i = 1; i <= m; ++i) { 
      const auto& [u, v, w] = edge[i];
      for (int type = 0; type < 2; ++type) { 
        int mi = get(u, v, type);
        if (mi >= MAXEDGE) continue;
        long long value = total - mi + w;
        cost[value & 1] = min(cost[value & 1], value);
      }
    }

    cout << (cost[0] == MAX ? -1 : cost[0]) << " " << (cost[1] == MAX ? -1 : cost[1]) << "\n";

    it = 0;
    for (int i = 1; i <= n; ++i) ad[i].clear();
  }
}