二分+kuskal

#include<bits/stdc++.h>
#define per(i,l,r) for(int i(r), i##end(l); i>=i##end; --i)
#define rep(i,l,r) for(int i(l), i##end(r); i<=i##end; ++i)
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 8000+10; int n, m, fa[maxn];
struct node{int from, to, w;}edge[maxn];
bool cmp(node x, node y) {return x.w < y.w;}
int find(int index) {if(fa[index]==index)return index; return fa[index] = find(fa[index]);}
int merge(int x, int y) {
	int fax = find(x), fay = find(y);
	return fax = fa[fay];
}
bool check(int mid, int tot = 0) {
	rep(i, 1, n) fa[i] = i;
	rep(i, 1, m) {
		if(tot == n-1 || edge[i].w > mid) break;
		(find(edge[i].from != find(edge[i].to))) && (merge(edge[i].from, edge[i].to), tot++);
	}
	return tot == (n-1);
}
int main() {
	cin >> n >> m;
	rep(i, 1, m) cin >> edge[i].from >> edge[i].to >> edge[i].w;
	sort(edge+1, edge+1+m, cmp);
	int l = 0, r = 1e9, ans = 1e9, mid;
	while((mid = l + r >> 1, l <= r)) check(mid) && (r=mid-1, ans=mid) || (l=mid+1);
	cout << n-1 << " " << ans;
	return 0;
}