#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,M=1e5+10;
const int INF=1e18;
const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
struct Edge{
    int u,v,w,op;
};
bool cmp(const Edge& x,const Edge &y){
    return x.w<y.w;
}
struct Node{
    int ls,rs,odd=INF,even=INF;
} t[N<<5];
int root[N];
int idx;
void clear(){
    for(int i=0;i<=idx;i++)t[i]={0,0,INF,INF};
}
void pushup(int p){
    t[p].odd=min(t[t[p].ls].odd,t[t[p].rs].odd);
    t[p].even=min(t[t[p].ls].even,t[t[p].rs].even);
}
int build(int l,int r){
    int p=++idx;
    if(l==r)return p;
    int mid=l+r>>1;
    t[p].ls=build(l,mid),t[p].rs=build(mid+1,r);
    pushup(p);
    return p;
}
int insert(int p,int l,int r,int x,int y){
    int q=++idx;
    t[q]=t[p];
    if(l==r){
        if(y&1)t[q].odd=min(t[q].odd,y);
        else t[q].even=min(t[q].even,y);
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid)t[q].ls=insert(t[p].ls,l,mid,x,y);
    else t[q].rs=insert(t[p].rs,mid+1,r,x,y);
    pushup(q);
    return q;
}
int query(int p,int l,int r,int ql,int qr,int op){
    if(l==r)return op==0?t[p].even:t[p].odd;
    int mid=l+r>>1;
    int res=INF;
    if(ql<=mid)res=min(res,query(t[p].ls,l,mid,ql,qr,op));
    if(qr>mid)res=min(res,query(t[p].rs,mid+1,r,ql,qr,op));
    return res;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<Edge> e;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e.push_back({u,v,w});
    }
    sort(e.begin(),e.end(),cmp);
    DSU dsu(n+1);
    int ans=0;
    vector<PII> adj[n+1];
    for(auto &[u,v,w,op]:e){
        if(dsu.same(u,v))continue;
        dsu.merge(u,v);
        op=1;
        ans+=w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for(int i=1;i<=n;i++)dsu.find(i);
    if(dsu.size(1)!=n){
        cout<<"-1 -1\n";
        return;
    }
    vector<int> ord(n+1),siz(n+1);
    int ts=0;
    function<void(int,int)> dfs1=[&](int u,int fa){
        ord[u]=++ts;
        siz[u]=1;
        for(auto [v,w]:adj[u]){
            if(v==fa)continue;
            dfs1(v,u);
            siz[u]+=siz[v];
        }
    };
    dfs1(1,0);
    vector<PII> g[n+1];
    for(auto [u,v,w,op]:e){
        if(!op){
            if(ord[u]>ord[v])g[ord[u]].push_back({ord[v],w});
            else g[ord[v]].push_back({ord[u],w});
        }
    }
    clear();
    for(int i=0;i<=n;i++)root[i]=0;
    for(int i=1;i<=n;i++){
        bool G=0;
        for(auto [v,w]:g[i]){
            if(!G)root[i]=insert(root[i-1],1,n,v,w);
            else root[i]=insert(root[i],1,n,v,w);
        }
    }
    int res=INF;
    function<void(int,int,bool)> dfs2=[&](int u,int fa,bool op){
        for(auto [v,w]:adj[u]){
            if(v==fa)continue;
            dfs2(v,u,op);
            int L=ord[v],R=ord[v]+siz[v]-1;
            // cout<<u<<" "<<v<<" "<<L<<" "<<R<<" "<<ord[v]<<"\n";
            int OP=w&1;
            if(!op&&L>1){
                int val=query(root[R],1,n,1,L-1,!OP);
                if(val!=INF)res=min(res,ans-w+val);
            }
            if(op&&R<n){
                int val=query(root[L],1,n,R+1,n,!OP);
                if(val!=INF)res=min(res,ans-w+val);
            }
        }
    };
    dfs2(1,0,0);
    clear();
    for(int i=0;i<=n;i++)root[i]=0;
    for(int i=n;i>=1;i--){
        bool G=0;
        for(auto [v,w]:g[i]){
            if(!G)root[i]=insert(root[i+1],1,n,v,w);
            else root[i]=insert(root[i],1,n,v,w);
        }
    }
    dfs2(1,0,1);
    if(res==INF)res=-1;
    if(ans&1)swap(ans,res);
    cout<<ans<<" "<<res<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}