贪心+并查集

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int x,y,t;
}node[110000];
int father[1100];
int n,m,i;
bool cmp(Node x,Node y){
    return x.t<y.t;
}
bool isfinish(){
    int ans=0;
    for (int k=1;k<=n;k++){
        if (father[k]==k) ans++;
        if (ans>1) return false;
    }
    return ans;
}
int find(int x){
    if (x!=father[x]) father[x]=find(father[x]);
    return father[x];
}
void add(int x,int y){
    x=find(x),y=find(y);
    if (x!=y) father[x]=y;
}
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) father[i]=i;
    for (i=1;i<=m;i++)
        scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].t);
    sort(node+1,node+n+1,cmp);
    for (i=1;i<n;i++) add(node[i].x,node[i].y);
    while (!isfinish() && i<=m) add(node[i].x,node[i].y),i++;
    if (i>m) printf("-1");
    else printf("%d",node[i-1].t);
    return 0;
}