#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int deg[N],pa[N],ti,sp[N],d[N][19],cal[N][19],a[N],dep[N];
vector<int> adj[N];
vector<tuple<int,int,int>> edge;
int root(int x){if(pa[x]==x) return x; return pa[x]=root(pa[x]);}
void merge(int w,int u,int v){
deg[u]++,deg[v]++;
ti++;
a[ti]=w;
if(deg[u]>=3 || deg[v]>=3 || root(u)==root(v)) sp[ti]=true,cal[ti][0]=1;
int ru=root(u),rv=root(v);
pa[ti]=pa[ru]=pa[rv]=ti;
adj[ti].push_back(ru);
if(rv!=ru) adj[ti].push_back(rv);
//cout<<a[ti] <<" ";
//cout<<sp[ti] <<" ";
//cout<<ti <<" " <<ru <<" " <<rv <<"\n";
d[ru][0]=ti,d[rv][0]=ti;
}
void dfs(int u,int p){
for(auto v:adj[u]){
if(v==p) continue;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int i=18;i>=0;i--) if(dep[d[v][i]]>=dep[u]) v=d[v][i];
if(u==v) return u;
for(int i=18;i>=0;i--) if(d[u][i]!=d[v][i]) u=d[u][i],v=d[v][i];
return d[u][0];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
ti=N-1;
for(int i=0;i<N;i++) pa[i]=i;
for(int i=0;i<M;i++){
edge.push_back({W[i],U[i],V[i]});
}
sort(edge.begin(),edge.end());
for(auto [w,u,v]:edge){
merge(w,u,v);
}
dfs(ti,ti);
d[ti][0]=ti;
for(int i=1;i<=18;i++) for(int j=0;j<=ti;j++){
cal[j][i]=cal[j][i-1]||cal[d[j][i-1]][i-1];
d[j][i]=d[d[j][i-1]][i-1];
}
}
int getMinimumFuelCapacity(int X, int Y) {
int tar=lca(X,Y);
//cout<<"LCA" <<X <<" " <<Y <<" " <<tar <<"\n";
if(sp[tar]) return a[tar];
for(int i=18;i>=0;i--){
if(!cal[tar][i]) tar=d[tar][i];
}
if(!sp[tar]) return -1;
return a[tar];
}
