#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
int N=1e5+50;
int n,m;
vector<array<int,3>>grane;
struct PersistentArray{
vector<vector<pair<int,int>>>a;
int tm=0;
PersistentArray(){}
PersistentArray(int n){a.assign(n,{{0,0}});}
PersistentArray(vector<int>b){int n=b.size();a.resize(n);for(int i=0;i<n;i++)a[i].pb({b[i],0});}
void Set(int i,int x){tm++;a[i].pb({x,tm});}
void Add(int i,int x){tm++;a[i].pb({a[i].back().fi+x,tm});}
int Get(int i,int t){
int l=0,r=(int)a[i].size()-1,res=0;
while(l<=r){
int mid=l+r>>1;
if(a[i][mid].se<=t)res=a[i][mid].fi,l=mid+1;
else r=mid-1;
}
return res;
}
int Getlast(int i){return a[i].back().fi;}
};
struct DSU{
PersistentArray par,sajz,ciklus,deg;
vector<array<int,4>>times;
DSU(){}
DSU(int n){
par=PersistentArray(n);
sajz=PersistentArray(vector<int>(n,1));
ciklus=PersistentArray(n);
deg=PersistentArray(n);
times.pb({0,0,0,0});
}
int FS(int u,int t){int p=par.Get(u,times[t][0]);if(p==0)return u;return FS(p,t);}
void US(int u,int v){
auto [t0,t1,t2,t3]=times.back();
int u1=u,v1=v;
deg.Add(u1,1);
deg.Add(v1,1);
u=FS(u,times.size()-1),v=FS(v,times.size()-1);
if(u==v){
ciklus.Set(u,1);
times.pb({par.tm,sajz.tm,ciklus.tm,deg.tm});
return;
}
int mx=max(deg.Get(u1,t3),deg.Get(v1,t3));
if(sajz.Get(u,t1)>sajz.Get(v,t1))swap(u,v);
par.Set(u,v);
sajz.Add(v,sajz.Get(v,t1));
if(mx>=3||ciklus.Get(v,t1))ciklus.Set(v,1);
times.pb({par.tm,sajz.tm,ciklus.tm,deg.tm});
}
int Getcomp(int u,int t){return FS(u,t);}
int Get(int u,int t){
u=FS(u,t);
return ciklus.Get(u,times[t][2]);
}
}dsu;
void init(int n1,int m1,vector<int>U,vector<int>V,vector<int>W){
n=n1,m=m1;
for(int i=0;i<m;i++)grane.pb({W[i],U[i],V[i]});
sort(grane.begin(),grane.end());
dsu=DSU(N);
for(auto [w,u,v]:grane){
dsu.US(u,v);
//printf("%i %i %i\n",u,v,w);
}
//printf("* %i\n",dsu.times.size());
}
int getMinimumFuelCapacity(int X, int Y){
int l=1,r=m,ind=-1;
while(l<=r){
int mid=l+r>>1;
if(dsu.Getcomp(X,mid)==dsu.Getcomp(Y,mid)&&dsu.Get(X,mid))ind=mid,r=mid-1;
else l=mid+1;
}
ind--;
//printf(" %i\n",ind);
if(ind<0)return -1;
return grane[ind][0];
}
