#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int inf=1e9+7;
int myc[N],dst[N],tme[N],deg[N];
vector<int> cmp[N],my[N];
void mrg(int u,int v,int w){
deg[u]++;deg[v]++;
if(myc[u]==myc[v]){
int c=myc[u];
tme[c]=min(tme[c],w);
}else{
int c1=myc[u],c2=myc[v];
if(cmp[c1].size()>cmp[c2].size())swap(c1,c2);
tme[c2]=min(tme[c2],max(tme[c1],w));
dst[c1]=w;
if(deg[u]>2||deg[v]>2)tme[c2]=min(tme[c2],w);
for(int i:cmp[c1]){
myc[i]=c2;
my[i].pb(c2);
cmp[c2].pb(i);
}
cmp[c1].clear();
}
}
void init(int n,int m,vector<int> u,vector<int> v,vector<int> w){
vector<int> idx;
for(int i=0;i<m;i++)idx.pb(i);
sort(idx.begin(),idx.end(),[&](int i,int j){return w[i]<w[j];});
for(int i=0;i<n;i++){
myc[i]=i;
cmp[i]={i};
dst[i]=inf;
tme[i]=inf;
my[i].pb(i);
}
for(int i:idx){
mrg(u[i],v[i],w[i]);
}
}
int getMinimumFuelCapacity(int x,int y){
int i=0,j=0,mn=0;
while(i<my[x].size()&&j<my[y].size()&&my[x][i]!=my[y][j]){
if(dst[my[x][i]]<dst[my[y][j]])mn=max(mn,dst[my[x][i]]),i++;
else mn=max(mn,dst[my[y][j]]),j++;
}
if(i==my[x].size()||j==my[y].size())return -1;
int ans=inf;
while(i<my[x].size()){
ans=min(ans,max(tme[my[x][i]],mn));
mn=dst[my[x][i]];
assert(j<my[y].size()&&my[x][i]==my[y][j]);
i++;j++;
}
return ans==inf?-1:ans;
}
