#include <bits/stdc++.h>
#include "swap.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct TR{
vector<vector<int> > e;
vector<array<int,20> > as;
vector<int> tag;
vector<int> dep;
vector<int> val;
int sz=0;
void init(int x){
e.resize(x);
as.resize(x);
dep.resize(x,-1);
val.resize(x,2e9);
sz=x;
}
void add(int cnt){
//cout << sz << " " << cnt << "\n";
e.push_back(vector<int>());
as.push_back(array<int,20>());
dep.push_back(-1);
val.push_back(cnt);
sz++;
}
void eg(int a,int b){
//cout << a << "e" << b << '\n';
e[a].push_back(b);
}
void dfs(int r,int f){
as[r][0]=f;
val[r]=min(val[r],val[f]);
dep[r]=dep[f]+1;
for(int i=1;i<20;i++){
as[r][i]=as[as[r][i-1]][i-1];
}
for(auto h:e[r]){
dfs(h,r);
}
}
int lca(int a,int b){
if(dep[a]>dep[b]){
swap(a,b);
}
for(int i=19;i>=0;i--){
if(dep[as[b][i]]>=dep[a]){
b=as[b][i];
}
}
for(int i=19;i>=0;i--){
if(as[b][i]!=as[a][i]){
a=as[a][i];
b=as[b][i];
}
}
return as[a][0];
}
}tr;
struct DSU{
vector<int> bo,tag;
int sz=0;
vector<int> deg;
void init(int n){
bo.resize(n);
iota(bo.begin(),bo.end(),0);
tag.resize(n);
deg.resize(n);
sz=n;
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
void merge(int x,int y,int cnt){
deg[x]++;
deg[y]++;
int u=(deg[x]>=3 || deg[y]>=3);
x=find(x);
y=find(y);
if(x==y){
if(tag[x]==0){
tag[x]=1;
tr.val[x]=cnt;
}
return;
}
tag.push_back(0);
bo.push_back(sz);
deg.push_back(0);
bo[x]=bo[y]=sz;
tag[sz]|=tag[x];
tag[sz]|=tag[y];
tag[sz]|=u;
if(!tag[sz]){
cnt=2e9;
}
tr.add(cnt);
tr.eg(sz,x);
tr.eg(sz,y);
sz++;
}
}dsu;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
dsu.init(n);
tr.init(n);
vector<pair<int,pair<int,int> > > eg;
for(int i=0;i<m;i++){
eg.push_back({w[i],{u[i],v[i]}});
}
sort(eg.begin(),eg.end());
for(auto h:eg){
dsu.merge(h.sc.fs,h.sc.sc,h.fs);
}
tr.tag=dsu.tag;
tr.dfs(tr.sz-1,tr.sz-1);
}
int getMinimumFuelCapacity(int x, int y) {
int u=tr.lca(x,y);
if(tr.val[u]>1.5e9){
return -1;
}
return tr.val[u];
}
