#include "swap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(v) begin(v), end(v)
#define REP(i,o,n) for(int i=o;i<n;i++)
using namespace std;
#include <vector>
int depth[400500];
struct dsu {
vector<int> vec;
vector<int> lead;
vector<pair<int,bool>> info;
dsu(int n=0){
vec.clear();
vec.resize(n+10,-1);
lead.clear();
lead.resize(n+10,-1);
info.clear();
info.resize(n+10,{0,false});
}
void init(int n=0){
vec.clear();
vec.resize(n+10,-1);
lead.clear();
lead.resize(n+10,-1);
info.clear();
info.resize(n+10,{0,false});
}
int depth(int n){
if(::depth[n]!=-1)return ::depth[n];
if(vec[n]==-1)return ::depth[n]=0;
return ::depth[n]=depth(vec[n])+1;
}
int leader(int n){
return lead[n]<0?n:lead[n]=leader(lead[n]);
}
void merge(int u, int v, int w, bool has_three){
u=leader(u),v=leader(v);
int idx=vec.size();
vec.pb(-1);
lead.pb(-1);
info.pb({w,has_three});
vec[u]=lead[u]=vec[v]=lead[v]=idx;
info[idx].se=info[idx].se || info[u].se || info[v].se || (u==v);
}
};
dsu d;
vector<int> aw[200100];
int lift[400500][20];
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
memset(depth,-1,sizeof depth);
d.init(N);
vector<pair<int,pair<int,int>>> vec;
REP(i,0,M){
vec.pb({W[i],{U[i],V[i]}});
}
sort(all(vec));
for(auto i:vec){
aw[i.se.fi].pb(i.fi);
aw[i.se.se].pb(i.fi);
d.merge(i.se.fi,i.se.se,i.fi,aw[i.se.fi].size()>=3 || aw[i.se.se].size() >= 3);
}
REP(i,0,d.vec.size())depth[i]=d.depth(i);
memset(lift,-1,sizeof lift);
REP(i,0,d.vec.size()){
lift[i][0]=d.vec[i];
}
REP(j,1,20){
REP(i,0,d.vec.size()){
if(lift[i][j-1]!=-1)lift[i][j]=lift[lift[i][j-1]][j-1];
}
}
REP(i,0,N+10){
sort(all(aw[i]));
}
}
int getMinimumFuelCapacity(int X, int Y) {
int x=X,y=Y;
REP(ix,0,20){
auto i=20-1-ix;
if(lift[X][i] != -1 && depth[lift[X][i]]>=depth[Y])X=lift[X][i];
}
swap(X,Y);
REP(ix,0,20){
auto i=20-1-ix;
if(lift[X][i] != -1 && depth[lift[X][i]]>=depth[Y])X=lift[X][i];
}
REP(ix,0,20){
auto i=20-1-ix;
if(lift[X][i]!=lift[Y][i] && lift[X][i]!=-1 && lift[Y][i]!=-1)X=lift[X][i],Y=lift[Y][i];
}
while(X!=Y && lift[X][0]!=-1 && lift[Y][0]!=-1){
X=lift[X][0];
Y=lift[Y][0];
}
if(X!=Y)return -1;
int base=d.info[X].fi;
int ext=2e9;
// if(aw[x].size()>1)ext=min(ext,aw[x][1]);
// if(aw[y].size()>1)ext=min(ext,aw[y][1]);
REP(ix,0,20){
auto i=20-1-ix;
if(lift[X][i]!=-1 && !d.info[lift[X][i]].se)X=lift[X][i],Y=lift[Y][i];
}
while(lift[X][0]!=-1 && !d.info[X].se)X=lift[X][0];
if(d.info[X].se)ext=min(ext,d.info[X].fi);
return (ext>1e9)?-1:max(ext,base);
}
