Travel in Hackerland

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

#define ff first
#define ss second
#define endl '\n'

const int N=1e5+5;

int n,m,q;
int par[N],T[N],x[N],y[N],k[N],l[N],r[N];
vector<int> mid[N];
set<int> ms[N];
pair<int,pair<int,int>> a[N];

int get_par(int x)
{
    while(par[x]!=x)
    {
        par[x]=par[par[x]];
        x=par[x];
    }
    return x;
}

void merge(int u,int v)
{
    int p1=get_par(u);
    int p2=get_par(v);
    if(p1==p2)
    {
        return;
    }
    if(ms[p1].size() < ms[p2].size())
    {
        swap(p1,p2);
    }
    for(auto &x:ms[p2])
    {
        ms[p1].insert(x);
    }
    ms[p2].clear();
    par[p2]=p1;
}

void reset()
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        ms[i].clear();
        ms[i].insert(T[i]);
    }
}

void apply(int id)
{
    merge(a[id].ss.ff,a[id].ss.ss);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin>>n>>m>>q;

    for(int i=1;i<=n;i++)
    {
        cin>>T[i];
    }

    for(int i=1;i<=m;i++)
    {
        cin>>a[i].ss.ff>>a[i].ss.ss>>a[i].ff;
    }
    sort(a+1,a+m+1);

    for(int i=1;i<=q;i++)
    {
        cin>>x[i]>>y[i]>>k[i];
        l[i]=1;
        r[i]=m+1;
    }

    bool done=0;
    while(!done)
    {
        done=1;
        reset();
        for(int i=1;i<=q;i++)
        {
            if(l[i]!=r[i])
            {
                done=0;
                int c_mid=(l[i]+r[i])>>1;
                mid[c_mid].push_back(i);
            }
        }
        for(int i=1;i<=m;i++)
        {
            apply(i);
            while(!mid[i].empty())
            {
                int id=mid[i].back();
                mid[i].pop_back();
                int p1=get_par(x[id]);
                int p2=get_par(y[id]);
                if(p1==p2 and (int)ms[p1].size()>=k[id])  // must be connected
                {
                    r[id]=i;
                }
                else
                {
                    l[id]=i+1;
                }
            }
        }
    }

    for(int i=1;i<=q;i++)
    {
        assert(l[i]==r[i]);
        if(r[i]<=m)
        {
            cout<<a[r[i]].ff<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
    }
}