#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 SegmentTree{

    struct Node{
        int l,r,odd,even;
    };
    vector<Node> t;
    void init(int n){
        t=vector<Node>(n<<2);
    }
    void pushup(int p){
        t[p].odd=min(t[p<<1].odd,t[p<<1|1].odd);
        t[p].even=min(t[p<<1].even,t[p<<1|1].even);
    }
    void build(int p,int l,int r){
        t[p]={l,r,INF,INF};
        if(l==r)return;
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        return;
    }
    void insert(int p,int x,int y){
        if(t[p].l==t[p].r){
            if(y&1)t[p].odd=min(t[p].odd,y);
            else t[p].even=min(t[p].even,y);
            return;
        }
        int mid=t[p].l+t[p].r>>1;
        if(x<=mid)insert(p<<1,x,y);
        else insert(p<<1|1,x,y);
        pushup(p);
    }
    int query(int p,int l,int r,int op){
        if(l<=t[p].l&&r>=t[p].r)return op==0?t[p].even:t[p].odd;
        int mid=t[p].l+t[p].r>>1;
        int res=INF;
        if(l<=mid)res=min(res,query(p<<1,l,r,op));
        if(r>mid)res=min(res,query(p<<1|1,l,r,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});
        }
    }
    int res=INF;
    vector<array<int,3>> E;
    function<void(int,int)> dfs2=[&](int u,int fa){
        for(auto [v,w]:adj[u]){
            if(v==fa)continue;
            dfs2(v,u);
            int L=ord[v],R=ord[v]+siz[v]-1;
            E.push_back({L,R,w});
        }
    };
    dfs2(1,0);
    sort(E.begin(),E.end(),[&](const auto &x,const auto &y){
        return x[1]<y[1];
    });
    SegmentTree seg;
    seg.init(n+1);
    seg.build(1,1,n);
    for(int i=1,j=0;i<=n;i++){
        for(auto [v,w]:g[i])seg.insert(1,v,w);
        while(j<E.size()&&E[j][1]==i){
            auto [L,R,w]=E[j++];
            bool op=(w&1);
            if(L>1){
                int val=seg.query(1,1,L-1,!op);
                if(val!=INF)res=min(res,ans-w+val);
            }
        }
    }
    for(int i=1;i<=n;i++)g[i].clear();
    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});
        }
    }
    sort(E.begin(),E.end());
    seg.init(n+1);
    seg.build(1,1,n);
    for(int i=n,j=E.size()-1;i>=1;i--){
        for(auto [v,w]:g[i])seg.insert(1,v,w);
        while(j>=0&&E[j][0]==i){
            auto [L,R,w]=E[j--];
            bool op=(w&1);
            if(R<n){
                int val=seg.query(1,R+1,n,!op);
                if(val!=INF)res=min(res,ans-w+val);
            }
        }
    }
    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;
}