#ifdef ONLINE_JUDGE
#include "swap.h"
#endif
#include <bits/stdc++.h>
using namespace std;
bool isgood[400002];
int sp[400002][20];
struct e{
int u,v,w;
bool operator<(const e &a)const{
return w<a.w;
}
};
vector<e>edge;
struct dsu{
int par[400002],root[400002];
void init(int n){
for(int i = 0; i <= n; i++){
par[i]=i;
root[i]=i;
}
}
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
}d;
int nodec,deg[400002],cost[400002],dep[400002];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
d.init(N);
for(int i = 0; i < M; i++)edge.push_back({U[i],V[i],W[i]});
sort(edge.begin(),edge.end());
nodec=N;
for(int i = 0; i < M; i++){
auto [u,v,w]=edge[i];
deg[u]++;deg[v]++;
int pu=d.find(u),pv=d.find(v),ru=d.root[pu],rv=d.root[pv];
if(pu!=pv){
int nxt=nodec++;
cost[nxt]=w;
isgood[nxt]=isgood[ru]|isgood[rv]|(deg[u]>=3)|(deg[v]>=3);
sp[ru][0]=nxt;sp[rv][0]=nxt;
sp[nxt][0]=nxt;
d.par[pu]=pv;
d.root[pv]=nxt;
}
else{
if(!isgood[ru]){
int nxt=nodec++;
cost[nxt]=w;
isgood[nxt]=1;
sp[ru][0]=nxt;
sp[nxt][0]=nxt;
d.root[pu]=nxt;
}
}
}
for(int i = nodec-1; i >= 0; i--){
if(sp[i][0]!=i)dep[i]=dep[sp[i][0]]+1;
else dep[i]=0;
for(int j = 1; j < 20; j++)sp[i][j]=sp[sp[i][j-1]][j-1];
}
}
int lca(int x, int y){
if(dep[x]<dep[y])swap(x,y);
for(int i = 19; i >= 0; i--){
if(dep[sp[x][i]]>=dep[y])x=sp[x][i];
}
if(x==y)return x;
for(int i = 19; i >= 0; i--){
if(sp[x][i]!=sp[y][i]){
x=sp[x][i];
y=sp[y][i];
}
}
return sp[x][0];
}
int getMinimumFuelCapacity(int X, int Y){
int l=lca(X,Y);
if(isgood[l])return cost[l];
for(int i = 19; i >= 0; i--){
if(!isgood[sp[l][i]])l=sp[l][i];
}
l=sp[l][0];
if(!isgood[l])return -1;
return cost[l];
}
