#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const int mod=1000000007;
const int MAXN=300010, LOG=19;
int n, m;
int par[LOG][MAXN], h[MAXN];
int dsu[MAXN], root[MAXN], deg[MAXN];
bool ok[MAXN];
int W[MAXN], N;
int getpar(int x){ return (dsu[x]==x?x:dsu[x]=getpar(dsu[x]));}
void init(int nn, int mm, vector<int> U, vector<int> V, vector<int> WW){
iota(dsu, dsu+MAXN, 0);
iota(root, root+MAXN, 0);
n=nn;
m=mm;
vector<pair<int, pii>> E(m);
for (int i=0; i<m; i++) E[i]={WW[i], {U[i], V[i]}};
sort(all(E));
N=n;
for (auto p:E){
int u=p.second.first, v=p.second.second, w=p.first;
int x=getpar(u), y=getpar(v);
// debug2(u, v)
// debug2(x, y)
deg[u]++;
deg[v]++;
if (x==y){
par[0][root[x]]=N;
root[x]=N;
ok[N]=1;
W[N++]=w;
}
else{
par[0][root[x]]=N;
par[0][root[y]]=N;
ok[N]=(ok[root[x]]|ok[root[y]]|(deg[u]==3)|(deg[v]==3));
dsu[y]=x;
root[x]=N;
W[N++]=w;
}
}
// for (int i=0; i<N; i++) cerr<<i<<" : "<<W[i]<<" "<<ok[i]<<" "<<par[0][i]<<"\n";
par[0][N-1]=N-1;
for (int j=1; j<LOG; j++) for (int i=0; i<N; i++) par[j][i]=par[j-1][par[j-1][i]];
for (int i=N-2; ~i; i--) h[i]=h[par[0][i]]+1;
}
int Lca(int x, int y){
if (h[x]<h[y]) swap(x, y);
for (int i=0; i<LOG; i++) if ((h[x]-h[y])&(1<<i)) x=par[i][x];
if (x==y) return x;
for (int i=LOG-1; ~i; i--) if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
return par[0][x];
}
int getMinimumFuelCapacity(int X, int Y){
if (!ok[N-1]) return -1;
int V=Lca(X, Y);
if (ok[V]) return W[V];
for (int i=LOG-1; ~i; i--) if (!ok[par[i][V]]) V=par[i][V];
return W[par[0][V]];
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
1
0 1
*/
