#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end()
using ll=long long;
struct PersUF{
int size;
int time=-1;
//時間,親,flg
vector<vector<array<int,3>>> tree;
PersUF(int sz){
size=sz;
tree.resize(sz,{{-1,-1,0}});
}
int root(int pos,int tim){
while(true){
int ok=0,ng=tree[pos].size();
while(ng-ok>1){
int mid=(ok+ng)/2;
if(tree[pos][mid][0]<=tim){
ok=mid;
}
else{
ng=mid;
}
}
if(tree[pos][ok][1]<0)return pos;
pos=tree[pos][ok][1];
}
}
int isok(int pos,int tim){
while(true){
int ok=0,ng=tree[pos].size();
while(ng-ok>1){
int mid=(ok+ng)/2;
if(tree[pos][mid][0]<=tim){
ok=mid;
}
else{
ng=mid;
}
}
if(tree[pos][ok][1]<0)return tree[pos][ok][2];
pos=tree[pos][ok][1];
}
}
bool same(int s,int t,int tim){
return root(s,tim)==root(t,tim);
}
void merge(int s,int t){
time++;
s=root(s,time);
t=root(t,time);
if(s==t){
if(tree[s].back()[2])return;
tree[s].emplace_back(tree[s].back());
tree[s].back()[0]=time;
tree[s].back()[2]=1;
return;
}
if(-tree[s].back()[1]<-tree[t].back()[1])swap(s,t);
tree[s].emplace_back(tree[s].back());
tree[t].emplace_back(tree[t].back());
tree[s].back()[0]=time;
tree[t].back()[0]=time;
tree[s].back()[1]+=tree[t].back()[1];
tree[t].back()[1]=s;
tree[s].back()[2]|=tree[t].back()[2];
}
};
vector<array<int,3>> edge;
PersUF uni(0);
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
uni=PersUF(N);
edge.resize(M);
rep(i,M){
edge[i]={W[i],U[i],V[i]};
}
sort(all(edge));
vector<int> cnt(N,0);
for(auto &[w,u,v]:edge){
uni.merge(u,v);
cnt[u]++;
cnt[v]++;
if(cnt[u]>=3||cnt[v]>=3){
int pos=uni.root(u,uni.time);
uni.tree[pos].back()[2]=1;
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int ng=-1,ok=uni.time+1;
while(ok-ng>1){
int mid=(ok+ng)/2;
bool can=0;
if(uni.same(X,Y,mid)){
if(uni.isok(X,mid))can=1;
}
if(can)ok=mid;
else ng=mid;
}
if(ok==uni.time+1)return -1;
return edge[ok][0];
}
