View Code of Problem 3859

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#include<list>
#include <ctime>
#include <stack>
#include <cassert>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long long type;
typedef unsigned long long ull;
#define pw(k) ((1ll)<<(k))
const double eps = 1e-8;
const ull hash1=201326611;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e3+10;
const int M = 1e6+10;
const int dif = 26;
const double PI = acos(-1.0);
inline void Mod(ll& x) { if (x >= mod) x -= mod; }
void BinaryBitset(int n) { cout << bitset<sizeof(int) * 4>(n) << endl; }
inline int getBinary(int x){int cnt=0; for(;x;x-=(x & (-x))) cnt++;return cnt;}

int n,m,parent[N];
struct node{
    int from,to,w;
}edge[M];

int find(int x){
    if (x != parent[x]) parent[x] = find(parent[x]);
    return parent[x];
}

bool cmp(node x,node y){
    return x.w<y.w;
}

void Kruskal(){
    ll ret=0; int cnt=0,mx=0;
    for(int i=1;i<=n;i++) parent[i]=i;
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=m;i++){
        if(cnt==n-1) break;
        int fx=find(edge[i].from),fy=find(edge[i].to);
        if(fx!=fy){
            parent[fx]=fy; cnt++; ret+=edge[i].w; mx=max(mx,edge[i].w);
        }
    }
    printf("%lld %d\n",ret,mx);
}

int main() {
#ifdef ACM_LOCAL
    freopen("./std.in","r",stdin);
#endif
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w);
        }
        Kruskal();
    }
    return 0;
}