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

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

struct dsu {
  dsu(int n) : tt(n + 1), sz(n + 1) {
    for (int i = 1; i <= n; ++i) {
      tt[i] = i;
      sz[i] = 1;
    }
  }

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

  void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if (sz[x] < sz[y]) {
      swap(x, y);
    }

    tt[y] = x;
    sz[x] += sz[y];
  }
  
  vector<int> tt, sz;
};

struct edge {
  int x, y, c;
  bool operator < (const edge &aux) const {
    return c < aux.c;
  }
};

struct bin_info {
  bin_info() : cp(-1), ci(-1) {}
  bin_info(ll x) {
    cp = ci = -1;
    if (x % 2 == 0) {
      cp = x;
    } else {
      ci = x;
    }
  }
  ll cp, ci;
};

bin_info max(const bin_info& x, const bin_info &y) {
  bin_info ret = x;
  ret.cp = max(ret.cp, y.cp);
  ret.ci = max(ret.ci, y.ci);
  return ret;
}

bin_info min(const bin_info& x, const bin_info &y) {
  bin_info ret = x;

  if (ret.cp == -1)
    ret.cp = y.cp;
  else if (ret.cp != -1)
    ret.cp = min(ret.cp, y.cp);

  if (ret.ci == -1)
    ret.ci = y.ci;
  else if (y.ci != -1)
    ret.ci = min(ret.ci, y.ci);

  return ret;
}

struct arb {
  arb(int n) : n(n), v(n + 1), tt(n + 1), c(n + 1), h(n + 1, 0) {

  }

  void add_edge(edge &it) {
    v[it.x].push_back({it.y, it.c});
    v[it.y].push_back({it.x, it.c});
  }

  void dfs(int nod, int papa = 0) {
    for (auto it : v[nod]) {
      if (it.first == papa)
        continue;

      tt[it.first] = nod;
      h[it.first] = h[nod] + 1;
      c[it.first] = it.second;
      dfs(it.first, nod);
    }
  }

  void build() {
    bl.resize(k);
    bt.resize(k);

    for (int i = 0; i < k; ++i) {
      bl[i].resize(n + 1);
      bt[i].resize(n + 1);
    }

    for (int i = 1; i <= n; ++i) {
      bt[0][i] = tt[i];
      bl[0][i] = bin_info(c[i]); 
    }

    for (int j = 1; j < k; ++j) {
      for (int i = 1; i <= n; ++i) {
        bt[j][i] = bt[j - 1][bt[j - 1][i]];
        bl[j][i] = max(bl[j - 1][i], bl[j - 1][bt[j - 1][i]]);
      }
    }
  }

  bin_info lca(int x, int y) {
    if (h[x] < h[y])
      swap(x, y);

    int dif = h[x];
    bin_info ans(-1);

    for (int j = 0; j < k && dif; ++j) {
      if ((1 << j) & dif) {
        ans = max(ans, bl[j][x]);
        x = bt[j][x];
        dif ^= (1 << j);
      }
    }

    for (int j = k - 1; j >= 0; --j) {
      if (bt[j][x] != bt[j][y]) {
        ans = max(ans, bl[j][x]);
        x = bt[j][x];
        ans = max(ans, bl[j][y]);
        y = bt[j][y];
      }
    }
    ans = max(ans, bl[0][x]);
    ans = max(ans, bl[0][y]);
    return ans;
  }

  const int k = 20;
  int n;
  vector<vector<pair<int, int>>> v;
  vector<int> tt;
  vector<int> c;
  vector<int> h;
  vector<vector<bin_info>> bl;
  vector<vector<int>> bt;
};

void solve() {

  int n, m;
  cin >> n >> m;

  vector<edge> e(m);

  for (auto& it : e) {
    cin >> it.x >> it.y >> it.c;
  }

  sort(e.begin(), e.end());

  dsu D(n);
  arb A(n);
  ll ans = 0; 
  for (auto it : e) {
    if (D.find(it.x) != D.find(it.y)) {
      D.unite(it.x, it.y);
      ans += it.c;
      A.add_edge(it);
    }
  }

  for (int i = 2; i <= n; ++i) {
    if (D.find(i) != D.find(1)) {
      cout << "-1 -1\n";
      return;
    }
  }

  A.dfs(1);
  A.build();

  bin_info fin(ans);
  for (auto it : e) {
    auto q = A.lca(it.x, it.y);

    if (q.cp != -1) {
      fin = min(fin, bin_info(ans - q.cp + it.c));
    }

    if (q.ci != -1) {
      fin = min(fin, bin_info(ans - q.ci + it.c));
    }
  }

  cout << fin.cp << " " << fin.ci << "\n";
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}