#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5;
int n,m;
vector<array<int,3> >isi;
int dsu[maxn+2],oke[maxn+2],deg[maxn+2],ans[maxn+2];
vector<int>adj[maxn+2];
int fin(int a){
if(dsu[a]==a)return a;
return dsu[a]=fin(dsu[a]);
}
void merg(int a,int b){
a=fin(a); b=fin(b);
if(a==b)return;
dsu[a]=b;
}
int bin[maxn+2][20],dep[maxn+2];
void dfs(int cur,int par){
bin[cur][0]=par;
dep[cur]=dep[par]+1;
for(auto x : adj[cur]){
if(x==par)continue;
dfs(x,cur);
oke[cur]|=oke[x];
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N,m=M;
for(int q=0;q<m;q++){
isi.push_back({W[q],U[q],V[q]});
}
sort(isi.begin(),isi.end());
for(int q=0;q<n+isi.size();q++)dsu[q]=q;
for(int q=0;q<isi.size();q++){
auto [we,u,v]=isi[q];
deg[u]++; deg[v]++;
if(fin(u)==fin(v)){
oke[n+q]=true;
adj[n+q].push_back(fin(u));
merg(u,n+q);
}
else{
if(deg[u]>=3 || deg[v]>=3){
oke[n+q]=true;
}
adj[n+q].push_back(fin(u)); adj[n+q].push_back(fin(v));
merg(u,n+q); merg(v,n+q);
}
ans[n+q]=we;
}
dfs(n+isi.size()-1,n+isi.size()-1);
for(int q=1;q<=19;q++){
for(int w=0;w<n+isi.size();w++){
bin[w][q]=bin[bin[w][q-1]][q-1];
}
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int slsh=dep[u]-dep[v];
for(int q=19;q>=0;q--){
if(slsh>=(1<<q)){
u=bin[u][q];
slsh-=(1<<q);
}
}
if(u==v)return u;
for(int q=19;q>=0;q--){
if(bin[u][q]!=bin[v][q]){
u=bin[u][q],v=bin[v][q];
}
}
return bin[u][0];
}
int getMinimumFuelCapacity(int x, int y) {
int apa=lca(x,y);
if(oke[apa])return ans[apa];
for(int q=19;q>=0;q--){
if(!oke[bin[apa][q]])apa=bin[apa][q];
}
apa=bin[apa][0];
//cout<<apa<<endl;
if(oke[apa])return ans[apa];
return -1;
}
