#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define endl "\n"
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f3f3f3f3f, mod = 1000000007;
typedef pair<int, int> PII;
int h[N], e[N], ne[N], w[N], idx;
int p[N];
int depth[N];
int fa[N][17], d1[N][17], d2[N][17];
int n, m;
struct Edge{
    int a, b, w;
    bool used;
    bool operator< (const Edge &t) const{
        return w < t.w;
    }
}edge[N];
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int kruskal(){
    int sum = 0;
    for(int i = 1; i <= n; i ++ ) p[i] = i;
    for(int i = 0; i < m; i ++ ){
        int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
        if (a != b)
        {
            p[a] = b;
            sum += w;
            edge[i].used = true;
        }
    }
    int x = find(1);
    for(int i = 2; i <= n; i ++ ) {
        if(find(i) != x) {
            return -1;
        }
    }
    return sum;
}
void build(){
    idx = 0;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++ ){
        if(edge[i].used){
            add(edge[i].a, edge[i].b, edge[i].w);
            add(edge[i].b, edge[i].a, edge[i].w);
        }
    }
}
void bfs(){
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    queue<int> q;
    q.push(1);
    while(q.size()){
        auto t = q.front();
        q.pop();

        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF;
                for(int k = 1; k <= 16; k ++ ){
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    int dist[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    d1[j][k] = d2[j][k] = -INF;
                    for(int u = 0; u < 4; u ++ ){
                        int d = dist[u];
                        if(d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if(d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                    }
                }
            }
        }
    }
}
int lca(int a, int b, int c){
    static int dist[N * 2];
    int cnt = 0;
    if(depth[a] < depth[b]) swap(a, b);
    for(int k = 16; k >= 0; k -- ){  // 将a和b跳到同一层
        if(depth[fa[a][k]] >= depth[b]){
            dist[cnt ++ ] = d1[a][k];
            dist[cnt ++ ] = d2[a][k];
            a = fa[a][k];
        }
    }
    if(a != b){
        for(int k = 16; k >= 0; k -- ){
            if(fa[a][k] != fa[b][k]){
                dist[cnt ++ ] = d1[a][k];
                dist[cnt ++ ] = d2[a][k];
                dist[cnt ++ ] = d1[b][k];
                dist[cnt ++ ] = d2[b][k];
                a = fa[a][k], b = fa[b][k];
            }
        }
        dist[cnt ++ ] = d1[a][0];
        dist[cnt ++ ] = d1[b][0];
        dist[cnt ++ ] = d2[a][0];
        dist[cnt ++ ] = d2[b][0];
    }
    sort(dist, dist + cnt);
    int dist1 = -INF, dist2 = -INF;
    for(int i = 0; i < cnt; i ++ ){
        if(dist[i] > dist1) dist2 = dist1, dist1 = dist[i];
        else if(dist[i] != dist1 && dist[i] > dist2) dist2 = dist[i];
    }
    if(c > dist1) return c - dist1;
    if(c > dist2) return c - dist2;
    return INF;
}
void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }
    sort(edge, edge + m);
    int sum = kruskal();
    if(sum == -1) {
        cout << "-1 -1\n";
        return;
    }
    build();
    bfs();
    int res = 1e18;
    for(int i = 0; i < m; i ++ ){
        if(!edge[i].used){
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            int t = sum + lca(a, b, w);
            if((sum - t) & 1) {
                res = min(res, t);
            }
        }
    }
    if(~sum & 1) {
        cout << sum << " " << (res == 1e18 ? -1 : res) << "\n";
    } else {
        cout << (res == 1e18 ? -1 : res) << " " << sum << "\n";
    }
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while(T -- ){
		solve();
	}
	return 0;
}