#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
const int NN=4e5+5;
int n,m,c,C=INT_MAX,dis[NN],lg[NN],f[NN];
vector<pair<int,int>> adj[NN];
pair<int,int> st[25][NN],par[25][NN];
bool cmp(pair<int,int> x,pair<int,int> y){
return x.S<y.S;
}
void dfs(int x,int p){
dis[x]=dis[p]+1;
st[0][++c]={dis[x],x};
f[x]=c;
for (auto u:adj[x]){
if (u.F==p) continue;
par[0][u.F]={x,u.S};
dfs(u.F,x);
st[0][++c]={dis[x],x};
}return;
}
void build(){
for (int i=1;i<25;i++) for (int j=1;j+(1<<i)<=2*n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
for (int i=1;i<25;i++){
for (int j=1;j<=n;j++){
par[i][j].F=par[i-1][par[i-1][j].F].F;
par[i][j].S=max(par[i-1][j].S,par[i-1][par[i-1][j].F].S);
}
}return;
}
int query(int l,int r){
if (l>r) swap(l,r);
int i=lg[r-l+1];
return min(st[i][l],st[i][r-(1<<i)+1]).S;
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W) {
for (int i=2;i<NN;i++) lg[i]=lg[i/2]+1;
n=N,m=M;dis[0]=-1;
for (int i=0;i<m;i++){
adj[U[i]+1].pb({V[i]+1,W[i]});
adj[V[i]+1].pb({U[i]+1,W[i]});
}
for (int i=1;i<=n;i++){
if (adj[i].size()<3) continue;
sort(adj[i].begin(),adj[i].end(),cmp);
C=min(C,adj[i][2].S);
}
dfs(1,0);
build();
return;
}
int getMinimumFuelCapacity(int x, int y) {
x++;y++;
int lca=query(f[x],f[y]);
int ans=C,ansx=0,ansy=0;
for (int i=0;i<25;i++) if ((dis[x]-dis[lca])&(1<<i)) ansx=max(ansx,par[i][x].S),x=par[i][x].F;
for (int i=0;i<25;i++) if ((dis[y]-dis[lca])&(1<<i)) ansy=max(ansy,par[i][y].S),y=par[i][y].F;
ans=max(ans,max(ansx,ansy));
if (ans==INT_MAX) return -1;
return ans;
}
