#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define gcd __gcd
using namespace std;
int uni[200005];
int _find(int x){
    if (x == uni[x]) return x;
    return uni[x] = _find(uni[x]);
}
void join(int x, int y){
    uni[_find(x)] = _find(y);
}
vector<pair<int, int> > g[200005];
int fa[200005][25];
int maxOdd[200005][25];
int maxEven[200005][25];
int dep[200005];
void dfs(int u, int ffa){
    for (int i = 1; dep[u] - (1 << i) >= 1; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        maxOdd[u][i] = max(maxOdd[u][i - 1], maxOdd[fa[u][i - 1]][i - 1]);
        maxEven[u][i] = max(maxEven[u][i - 1], maxEven[fa[u][i - 1]][i - 1]);
    }
    for (auto [v, w] : g[u]){
        if (v == ffa) continue;
        fa[v][0] = u;
        if (w & 1ll){
            maxOdd[v][0] = w;
            maxEven[v][0] = 0;
        }
        else {
            maxEven[v][0] = w;
            maxOdd[v][0] = 0;
        }
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--){
        if (dep[fa[u][i]] >= dep[v]){
            u = fa[u][i];
        }
        if (u == v) return u;
    }
    for (int i = 20; i >= 0; i--){
        if (fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
int getMaxOdd(int u, int v){
    int f = lca(u, v);
    int maxn = 0;
    int d = dep[u] - dep[f];
    int p = u;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxOdd[p][bit]);
            p = fa[p][bit];
        }
    }
    d = dep[v] - dep[f];
    p = v;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxOdd[p][bit]);
            p = fa[p][bit];
        }
    }
    return maxn;
}
int getMaxEven(int u, int v){
    int f = lca(u, v);
    int maxn = 0;
    int d = dep[u] - dep[f];
    int p = u;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxEven[p][bit]);
            p = fa[p][bit];
        }
    }
    d = dep[v] - dep[f];
    p = v;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxEven[p][bit]);
            p = fa[p][bit];
        }
    }
    return maxn;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        int n, m;
        cin >> n >> m;
        vector< array<int, 3> > e(m + 5);
        vector<int> vis(m + 5);
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 3; j++){
                cin >> e[i][j];
            }
        }
        sort(e.begin() + 1, e.begin() + m + 1, [&](array<int, 3> x, array<int, 3> y){
            return x[2] < y[2];
        });
        int cnt = 0;
        for (int i = 1; i <= n; i++){
            uni[i] = i;
            g[i].clear();
        }
        int sum = 0;
        for (int i = 1; i <= m; i++){
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if (_find(u) == _find(v)) continue;
            vis[i] = 1;
            join(u, v);
            cnt++;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            sum += w;
        }
        if (cnt != n - 1) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        dep[1] = 1;
        dfs(1, 1);
        int odd = LLONG_MAX, even = LLONG_MAX;
        int flag = 0;
        if (sum & 1ll) odd = sum;
        else even = sum, flag++;
        for (int i = 1; i <= m; i++){
            if (vis[i]) continue;
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if (w & 1ll){
                int res = getMaxEven(u, v);
                if (!res) continue;
                int anw = sum - res + w;
                assert(anw >= sum);
                odd = min(odd, sum - res + w);
                even = min(even, sum - res + w);
            }
            else {
                int res = getMaxOdd(u, v);
                if (!res) continue;
                int anw = sum - res + w;
                assert(anw >= sum);
                odd = min(odd, sum - res + w);
                even = min(even, sum - res + w);
            }
        }
        if (even == LLONG_MAX) even = -1;
        if (odd == LLONG_MAX) odd = -1;
        cout << even << ' ' << odd << endl;
    }
    return 0;
}#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define gcd __gcd
using namespace std;
int uni[200005];
int _find(int x){
    if (x == uni[x]) return x;
    return uni[x] = _find(uni[x]);
}
void join(int x, int y){
    uni[_find(x)] = _find(y);
}
vector<pair<int, int> > g[200005];
int fa[200005][25];
int maxOdd[200005][25];
int maxEven[200005][25];
int dep[200005];
void dfs(int u, int ffa){
    for (int i = 1; dep[u] - (1 << i) >= 1; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        maxOdd[u][i] = max(maxOdd[u][i - 1], maxOdd[fa[u][i - 1]][i - 1]);
        maxEven[u][i] = max(maxEven[u][i - 1], maxEven[fa[u][i - 1]][i - 1]);
    }
    for (auto [v, w] : g[u]){
        if (v == ffa) continue;
        fa[v][0] = u;
        if (w & 1){
            maxOdd[v][0] = w;
            maxEven[v][0] = 0;
        }
        else {
            maxEven[v][0] = w;
            maxOdd[v][0] = 0;
        }
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--){
        if (dep[fa[u][i]] >= dep[v]){
            u = fa[u][i];
        }
        if (u == v) return u;
    }
    for (int i = 20; i >= 0; i--){
        if (fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
int getMaxOdd(int u, int v){
    int f = lca(u, v);
    int maxn = 0;
    int d = dep[u] - dep[f];
    int p = u;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxOdd[p][bit]);
            p = fa[p][bit];
        }
    }
    d = dep[v] - dep[f];
    p = v;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxOdd[p][bit]);
            p = fa[p][bit];
        }
    }
    return maxn;
}
int getMaxEven(int u, int v){
    int f = lca(u, v);
    int maxn = 0;
    int d = dep[u] - dep[f];
    int p = u;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxEven[p][bit]);
            p = fa[p][bit];
        }
    }
    d = dep[v] - dep[f];
    p = v;
    for (int bit = 20; bit >= 0; bit--){
        if (d >> bit & 1){
            maxn = max(maxn, maxEven[p][bit]);
            p = fa[p][bit];
        }
    }
    return maxn;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        int n, m;
        cin >> n >> m;
        vector< array<int, 3> > e(m + 5);
        vector<int> vis(m + 5);
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 3; j++){
                cin >> e[i][j];
            }
        }
        sort(e.begin() + 1, e.begin() + m + 1, [&](array<int, 3> x, array<int, 3> y){
            return x[2] < y[2];
        });
        int cnt = 0;
        for (int i = 1; i <= n; i++){
            uni[i] = i;
            g[i].clear();
        }
        int sum = 0;
        for (int i = 1; i <= m; i++){
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if (_find(u) == _find(v)) continue;
            vis[i] = 1;
            join(u, v);
            cnt++;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            sum += w;
        }
        if (cnt != n - 1) {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        dep[1] = 1;
        dfs(1, 1);
        int odd = LLONG_MAX, even = LLONG_MAX;
        int flag = 0;
        if (sum & 1ll) odd = sum;
        else even = sum, flag++;
        for (int i = 1; i <= m; i++){
            if (vis[i]) continue;
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if (w & 1ll){
                int res = getMaxEven(u, v);
                if (!res) continue;
                int anw = sum - res + w;
                if (flag && anw >= even) odd = min(odd, sum - res + w);
                if (!flag && anw >= odd) even = min(even, sum - res + w);
            }
            else {
                int res = getMaxOdd(u, v);
                if (!res) continue;
                int anw = sum - res + w;
                if (flag && anw >= even) odd = min(odd, sum - res + w);
                if (!flag && anw >= odd) even = min(even, sum - res + w);
            }
        }
        if (even == LLONG_MAX) even = -1;
        if (odd == LLONG_MAX) odd = -1;
        cout << even << ' ' << odd << endl;
    }
    return 0;
}

answer.code:167:2: error: stray ‘#’ in program
  167 | }#include <bits/stdc++.h>
      |  ^
answer.code:167:3: error: ‘include’ does not name a type
  167 | }#include <bits/stdc++.h>
      |   ^~~~~~~
answer.code:172:5: error: redefinition of ‘long long int uni [200005]’
  172 | int uni[200005];
      |     ^~~
answer.code:6:5: note: ‘long long int uni [200005]’ previously declared here
    6 | int uni[200005];
      |     ^~~
answer.code:173:5: error: redefinition of ‘long long int _find(long long int)’
  173 | int _find(int x){
      |     ^~~~~
answer.code:7:5: note: ‘long long int _find(long long int)’ previously defined here
    7 | int _find(int x){
      |     ^~~~~
answer.code:177:6: error: redefinition of ‘void join(long long int, long long int)’
  177 | void join(int x, int y){
      |      ^~~~
answer.code:11:6: note: ‘void join(long long int, long long int)’ previously defined here
   11 | void join(int x, int y){
      |      ^~~~
answer.code:180:25: error: redefinition of ‘std::vector<std::pair<long long int, long long int> > g [200005]’
  180 | vector<pair<int, int> > g[200005];
      |                         ^
answer.code:14:25: note: ‘std::vector<std::pair<long long int, long long int> > g [200005]’ previously declared here
   14 | vector<pair<int, int> > g[200005];
      |                         ^
answer.code:181:5: error: redefinition of ‘long long int fa [200005][25]’
  181 | int fa[200005][25];
      |     ^~
answer.code:15:5: note: ‘long long int fa [200005][25]’ previously declared here
   15 | int fa[200005][25];
      |     ^~
answer.code:182:5: error: redefinition of ‘long long int maxOdd [200005][25]’
  182 | int maxOdd[200005][25];
      |     ^~~~~~
answer.code:16:5: note: ‘long long int maxOdd [200005][25]’ previously declared here
   16 | int maxOdd[200005][25];
      |     ^~~~~~
answer.code:183:5: error: redefinition of ‘long long int maxEven [200005][25]’
  183 | int maxEven[200005][25];
      |     ^~~~~~~
answer.code:17:5: note: ‘long long int maxEven [200005][25]’ previously declared here
   17 | int maxEven[200005][25];
      |     ^~~~~~~
answer.code:184:5: error: redefinition of ‘long long int dep [200005]’
  184 | int dep[200005];
      |     ^~~
answer.code:18:5: note: ‘long long int dep [200005]’ previously declared here
   18 | int dep[200005];
      |     ^~~
answer.code:185:6: error: redefinition of ‘void dfs(long long int, long long int)’
  185 | void dfs(int u, int ffa){
      |      ^~~
answer.code:19:6: note: ‘void dfs(long long int, long long int)’ previously defined here
   19 | void dfs(int u, int ffa){
      |      ^~~
answer.code:206:5: error: redefinition of ‘long long int lca(long long int, long long int)’
  206 | int lca(int u, int v){
      |     ^~~
answer.code:40:5: note: ‘long long int lca(long long int, long long int)’ previously defined here
   40 | int lca(int u, int v){
      |     ^~~
answer.code:222:5: error: redefinition of ‘long long int getMaxOdd(long long int, long long int)’
  222 | int getMaxOdd(int u, int v){
      |     ^~~~~~~~~
answer.code:56:5: note: ‘long long int getMaxOdd(long long int, long long int)’ previously defined here
   56 | int getMaxOdd(int u, int v){
      |     ^~~~~~~~~
answer.code:243:5: error: redefinition of ‘long long int getMaxEven(long long int, long long int)’
  243 | int getMaxEven(int u, int v){
      |     ^~~~~~~~~~
answer.code:77:5: note: ‘long long int getMaxEven(long long int, long long int)’ previously defined here
   77 | int getMaxEven(int u, int v){
      |     ^~~~~~~~~~
answer.code:264:8: error: redefinition of ‘int main()’
  264 | signed main(){
      |        ^~~~
answer.code:98:8: note: ‘int main()’ previously defined here
   98 | signed main(){
      |        ^~~~