#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
const int MAXN=100005,MAXM=200005,LOG=19;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
int par[MAXN+MAXM],deg[MAXN],cost[MAXN+MAXM],N,depth[MAXN+MAXM],pa[LOG][MAXN+MAXM];
bool bisaswap[MAXN+MAXM];
vector<piii> edges;
vector<int> adj[MAXN+MAXM];
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
int LCA(int u,int v){
if(depth[u]<depth[v])swap(u,v);
int diff=depth[u]-depth[v];
for(int i=LOG-1;i>=0;i--){
if(diff & (1<<i))u=pa[i][u];
}
if(u==v)return u;
for(int i=LOG-1;i>=0;i--){
if(pa[i][u]!=pa[i][v]){
u=pa[i][u];
v=pa[i][v];
}
}
return pa[0][u];
}
void dfs(int now){
for(auto nxt : adj[now]){
pa[0][nxt]=now;
for(int i=1;i<LOG;i++)pa[i][nxt]=pa[i-1][pa[i-1][nxt]];
depth[nxt]=depth[now]+1;
dfs(nxt);
}
}
void init(int n, int m,
vector<int> U, vector<int> V, vector<int> W) {
N=n;
for(int i=0;i<m;i++){
U[i]++;V[i]++;
edges.push_back({W[i],{U[i],V[i]}});
}
for(int i=1;i<=N;i++){
par[i]=i;
deg[i]=0;
bisaswap[i]=false;
}
sort(edges.begin(),edges.end());
for(auto isi : edges){
int ortua=find(isi.se.fi),ortub=find(isi.se.se);
deg[isi.se.fi]++;
deg[isi.se.se]++;
N++;
par[N]=N;
par[ortua]=N;
par[ortub]=N;
if(ortua==ortub){
bisaswap[N]=true;
}
else if(bisaswap[ortua] || bisaswap[ortub] || deg[isi.se.fi]>=3 || deg[isi.se.se]>=3){
bisaswap[N]=true;
}
cost[N]=isi.first;
adj[N].push_back(ortua);
if(ortua!=ortub)adj[N].push_back(ortub);
}
dfs(N);
}
int getMinimumFuelCapacity(int X, int Y) {
if(!bisaswap[N])return -1;
X++;Y++;
int anc=LCA(X,Y);
if(bisaswap[anc])return cost[anc];
for(int i=LOG-1;i>=0;i--){
if((1<<i)>depth[anc])continue;
if(!bisaswap[pa[i][anc]]){
anc=pa[i][anc];
}
}
return cost[pa[0][anc]];
}
