#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
const int maxn = 2e5+5;
const int maxl = 20;
#define pii pair<int,int>
#define fi first
#define se second
vector<pii> edge[maxn];
int dep[maxn],par[maxn][maxl],Min[maxn][maxl],Max[maxn][maxl];
struct DSU{
int par[maxn];
void init(int n){
for(int i=1;i<=n;i++) par[i]=i;
}
int findpar(int u){
if(u!=par[u]) return par[u]=findpar(par[u]);
return u;
}
bool unions(int u,int v){
u=findpar(u);v=findpar(v);
if(u==v) return false;
return par[v]=u,true;
}
}dsu;
void dfs(int u,int p){
dep[u]=dep[p]+1;
par[u][0]=p;Min[u][0]=inf;
for(int i=1;i<18;i++){
par[u][i]=par[par[u][i-1]][i-1];Min[u][i]=inf;
Max[u][i]=max(Max[u][i-1],Max[par[u][i-1]][i-1]);
}
for(auto [v,w]:edge[u]) if(v!=p) Max[v][0]=w,dfs(v,u);
}
void update(int u,int v,int w){
if(dep[u]>dep[v]) swap(u,v);
for(int i=0;i<18;i++){
if((dep[v]-dep[u])>>i&1){
Min[v][i]=min(Min[v][i],w);
v=par[v][i];
}
}
if(u==v) return;
for(int i=17;i>=0;i--){
if(par[u][i]!=par[v][i]){
Min[v][i]=min(Min[v][i],w);
Min[u][i]=min(Min[u][i],w);
u=par[u][i];v=par[v][i];
}
}
Min[u][0]=min(Min[u][0],w);
Min[v][0]=min(Min[v][0],w);
}
int query(int u,int v){
int res=inf,mx=0;
if(dep[u]>dep[v]) swap(u,v);
for(int i=0;i<18;i++){
if((dep[v]-dep[u])>>i&1){
res=min(res,Min[v][i]);
mx=max(mx,Max[v][i]);
v=par[v][i];
}
}
if(u==v) return max(res,mx);
for(int i=17;i>=0;i--){
if(par[u][i]!=par[v][i]){
res=min(res,Min[v][i]);
res=min(res,Min[u][i]);
mx=max(mx,Max[v][i]);
mx=max(mx,Max[u][i]);
u=par[u][i];v=par[v][i];
}
}
res=min(res,Min[u][0]);
res=min(res,Min[v][0]);
mx=max(mx,Max[u][0]);
mx=max(mx,Max[v][0]);
return max(res,mx);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
dsu.init(N);
vector<int> ord(M);
iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int x,int y){
return W[x]<W[y];
});
vector<int> cc;
for(int i:ord){
U[i]++;V[i]++;
if(dsu.unions(U[i],V[i])){
edge[U[i]].push_back({V[i],W[i]});
edge[V[i]].push_back({U[i],W[i]});
}
else cc.push_back(i);
}
dfs(1,0);
for(int i:cc) update(U[i],V[i],W[i]);
for(int i=16;i>=0;i--){
for(int u=1;u<=N;u++){
Min[u][i]=min(Min[u][i],Min[u][i+1]);
Min[par[u][i]][i]=min(Min[par[u][i]][i],Min[u][i+1]);
}
}
for(int i=1;i<18;i++){
for(int u=1;u<=N;u++) Min[u][i]=min(Min[u][i-1],Min[par[u][i-1]][i-1]);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int val=query(X+1,Y+1);
if(val==inf) return -1;
else return val;
}
