SBMST

#include <bits/stdc++.h>
#ifdef TEST
    #define debug(...) printf(__VA_ARGS__)
#else
    #define debug(...) (void)0
#endif
#define EB emplace_back
#define MP make_pair
#define ST first
#define ND second
using namespace std;
using ll = long long;
using llu = long long unsigned;
using pii = pair<int,int>;
/************************/
#define MAX 100
using Edge = tuple<int, int, int>; // Edge represented by (w, a, b)
using Mst = pair<vector<int>, int>; // contain point set & size
int n, m;
struct disjoint{
    int arr[MAX+5];
    disjoint(){
        for(int i = 0 ; i < MAX+5; ++i)
            arr[i] = i;
    }
    int find(int n){return arr[n] = (arr[n] == n)?n:find(arr[n]);}
    void Union(int a, int b){arr[find(b)] = find(a);}
};
Mst kruskal(vector<Edge> &g, int ignore=-1){
    vector<int> s;
    int sum = 0;
    disjoint dj;// core disjoint set
    for(int i = 0 ; i < int(g.size()) ; ++i){
        int a, b, w; // edge on a and b, weight = w
        tie(w, a, b) = g[i];
        // not in the same set
        if(dj.find(a) != dj.find(b) && (ignore < 0 || ignore != i)){
            s.EB(i);
            sum += w;
            dj.Union(a, b);  // union in the set
        }
    }
    return (int(s.size()) >= n-1)? MP(s, sum): MP(s, numeric_limits<int>::max());
}
int sbmst(Mst &mst, vector<Edge> &graph){
    int sbmst_sz = numeric_limits<int>::max();
    for(auto it = mst.ST.begin(); it != mst.ST.end(); ++it){
        Mst tmp = kruskal(graph, *it);
        if(tmp.ND < sbmst_sz){
            sbmst_sz = tmp.ND;
        }
    }
    return sbmst_sz;
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        vector<Edge> graph;
        scanf("%d%d", &n, &m);
        for(int i = 0 ; i < m; ++i){
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);
            graph.EB(w, a, b);
        }
        sort(graph.begin(), graph.end());
        Mst mst = kruskal(graph);
        int sbmst_sz = sbmst(mst, graph);
        printf("%d %d\n", mst.ND, sbmst_sz);
    }
    return 0;
}