#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<int> u;
vector<int> v;
vector<int> w;
vector<pair<int,int>> sm;
int n;
int m;
vector<int> rt;
vector<int> sz;
vector<int> fr;
vector<int> jk;
int find(int u){
if(rt[u]!=u){
rt[u]=find(rt[u]);
if(fr[u] or jk[u]>=3)fr[rt[u]]=1;
}
return rt[u];
}
bool unite(int a, int b){
a=find(a);
b=find(b);
if(a==b){
fr[a]=1;
return false;
}
if(sz[a]>=sz[b]){
sz[a]+=sz[b];
if(fr[b])fr[a]=1;
rt[b]=a;
}
else{
sz[b]+=sz[a];
if(fr[a])fr[b]=1;
rt[a]=b;
}
return true;
}
bool fk=false;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
u=U;
v=V;
w=W;
n=N;
m=M;
vector<int> pl(n);
if(m==n-1){
fk=true;
for(int i=0;i<m;i++){
pl[u[i]]++;
pl[v[i]]++;
}
for(auto i:pl){
if(i>=3)fk=false;
}
}
for(int i=0;i<M;i++){
sm.push_back({w[i],i});
}
sort(sm.begin(),sm.end());
fr.resize(n,0);
sz.resize(n,1);
jk.resize(n);
rt.resize(n);
}
int getMinimumFuelCapacity(int X, int Y) {
if(fk)return -1;
for(int i=0;i<n;i++){
rt[i]=i;
sz[i]=1;
jk[i]=0;
fr[i]=0;
}
int ans=0;
for(int i=0;i<m;i++){
jk[u[sm[i].second]]++;
jk[v[sm[i].second]]++;
if(jk[u[sm[i].second]]>=3)fr[u[sm[i].second]]=1;
if(jk[v[sm[i].second]]>=3)fr[v[sm[i].second]]=1;
bool ko=unite(u[sm[i].second],v[sm[i].second]);
ans=sm[i].first;
if(find(X)==find(Y) and fr[find(X)])break;
}
return ans;
}
