#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct DSU{
    vector<int> fa;
    void init(int n){fa.resize(n+1);rep(i,1,n)fa[i]=i;}
    int find(int x){
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        int fx=find(x),fy=find(y);
        fa[fy]=fx;
    }
};
vector<vector<int>> G;
vector<int> fa,sz,son,dep,top;
vector<int> a[2],f[2][20],par[20];
void dfs1(int x){
    sz[x]=1;
    for(auto to:G[x])if(to!=fa[x]){
        fa[to]=x;
        dep[to]=dep[x]+1;
        dfs1(to);
        sz[x]+=sz[to];
        if(sz[to]>sz[son[x]])son[x]=to;
    }
}
void dfs2(int x,int t){
    top[x]=t;
    if(son[x])dfs2(son[x],t);
    for(auto to:G[x])if(to!=son[x]&&to!=fa[x])dfs2(to,to);
}
int lca(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]])swap(a,b);
        a=fa[top[a]];
    }
    if(dep[a]<dep[b])swap(a,b);
    return b;
}

void solve(){
    int n,m;
    cin>>n>>m;
    fa=sz=son=dep=top=vector<int> (n+1);
    G=vector<vector<int>>(n+1);
    a[0]=vector<int>(n+1,-1);
    a[1]=vector<int>(n+1,-1);
    rep(odd,0,1)rep(d,0,19)f[odd][d]=vector<int>(n+1,0);
    rep(d,0,19)par[d]=vector<int>(n+1,0);
    
    DSU dsu;dsu.init(n);
    vector<array<int,3>> E;
    rep(i,1,m){
        int u,v,w;
        cin>>u>>v>>w;
        E.push_back({w,u,v});
    }
    sort(E.begin(),E.end());
    vector<bool> used(m);
    long long sum=0;
    for(int i=0;i<m;i++){
        auto [w,u,v]=E[i];
        if(dsu.find(u)==dsu.find(v))continue;
        G[u].push_back(v);
        G[v].push_back(u);
        dsu.merge(u,v);
        sum+=w;
        used[i]=true;
    }
    int block=0;
    rep(i,1,n)if(dsu.find(i)==i)block++;
    if(block!=1){
        cout<<-1<<' '<<-1<<endl;
        return;
    }
    long long ans[2];
    int p=(sum&1);
    // cout<<"sum="<<sum<<endl;
    ans[p]=sum;ans[p^1]=std::numeric_limits<long long>::max();
    dfs1(1);dfs2(1,1);//fa[1]=0;
    
    for(int i=0;i<m;i++){
        if(used[i]){
            auto [w,u,v]=E[i];
            if(fa[u]==v)a[w&1][u]=w;
            else a[w&1][v]=w;
        }
    }
    rep(i,1,n)rep(o,0,1)f[o][0][i]=a[o][i];
    rep(i,1,n)par[0][i]=fa[i];
    
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            par[j][i]=par[j-1][par[j-1][i]];
            for(int o=0;o<=1;o++)f[o][j][i]=max(f[o][j-1][i],f[o][j-1][par[j-1][i]]);
        }
    }
    auto calc=[&](int a,int b,int o){//a to b
        int v=dep[a]-dep[b],ans=-1;
        v--;
        for(int j=19;j>=0;j--){
            if(v>=(1<<j)){
                ans=max(ans,f[o][j][a]);
                a=par[j][a];
                v-=(1<<j);
            }
        }
        ans=max(ans,f[o][0][a]);
        return ans;
    };
    // cout<<"fa:";rep(i,1,n)cout<<fa[i]<<' ';cout<<endl;
    // cout<<"fa:";rep(i,1,n)cout<<top[i]<<' ';cout<<endl;

    for(int i=0;i<m;i++){
        if(!used[i]){
            auto [w,u,v]=E[i];
            // cout<<"work on "<<u<<' '<<v<<endl;
            int L=lca(u,v);
            // cout<<"L="<<L<<endl;
            int mx=max(calc(u,L,(w&1)^1),calc(v,L,(w&1)^1));
            if(mx!=-1)ans[p^1]=min(ans[p^1],ans[p]+w-mx);
        }
    }
    if(ans[p^1]==std::numeric_limits<long long>::max())ans[p^1]=-1;
    cout<<ans[0]<<' '<<ans[1]<<endl;
}
int main(){
    fastio;
    int tc;cin>>tc;
    while(tc--)solve();
    return 0;
}