wormsort.cpp

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;

int pai[MAXN], tam[MAXN];

int achar(int a){
    if(pai[a]==a)return a;
    return pai[a]=achar(pai[a]);
}

void juntar(int a, int b){
    a=achar(a);
    b=achar(b);
    if(a==b)return;
    if(tam[a]<tam[b])swap(a, b);
    pai[b]=a;
    tam[a]+=tam[b];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("wormsort.in", "r", stdin);
    freopen("wormsort.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grupos;
    vector<bool> usou(n+3);

    vector<int> pos(n+3);
    for(int i=1; i<=n; i++)
        cin >> pos[i];

    vector<pair<int,pair<int,int>>> tuneis;

    for(int i=0; i<m; i++){
        int w, a, b;
        cin >> a >> b >> w;
        tuneis.push_back({w, {a, b}});
    }

    sort(tuneis.rbegin(), tuneis.rend());

    for(int i=1; i<=n; i++){
        if(usou[i])continue;
        vector<int> cur;

        int ptr=i;

        while(1){
            if(usou[pos[ptr]])break;
            usou[pos[ptr]]=true;
            cur.push_back(pos[ptr]);
            ptr=pos[ptr];
        }

        grupos.push_back(cur);
    }

    if(grupos.size()==n){
        cout << -1 << endl;
        return 0;
    }

    int ini=0, fim=1000000000, resp;

    while(ini<=fim){
        for(int i=1; i<=n; i++){
            pai[i]=i;
            tam[i]=1;
        }
        int mid=(ini+fim)>>1;

        for(auto t:tuneis){
            if(t.first<mid)break;
            juntar(t.second.first, t.second.second);
        }

        bool teste=true;

        for(auto g:grupos){
            for(int i=0; i<g.size(); i++){
                if(achar(g[0])!=achar(g[i])){
                    teste=false;
                    break;
                }
            }
            if(!teste)break;
        }

        if(teste){
            ini=mid+1;
            resp=mid;
        }
        else fim=mid-1;
    }

    cout << resp << endl;

    return 0;
}