#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=1e5+5,MAXA=1e6+5,inf=2e9+5,MOD=982451653;
struct node{
bool cycle=0,deg3=0;
int p;
};
struct edge{
int w,u,v;
friend bool operator<(edge a,edge b){
return a.w<b.w;
}
};
node par[N];
vector<edge> e;
vector<pair<int,int>> adj[N];
bool good[N];
int on,deg[N],depth[N];
pair<int,int> up[N][20];
int find(int x){
return par[x].p=(par[x].p==x?x:find(par[x].p));
}
void merge(int a,int b,int cur){
a=find(a); b=find(b);
if(a==b){
adj[a].pb({on,-1}); good[on]=1;
adj[on++].pb({a,-1});
par[a].cycle=1;
return;
}
par[a].p=b;
adj[a].pb({on,cur});
adj[b].pb({on,cur});
adj[on].pb({a,cur});
adj[on].pb({b,cur});
}
void dfs(int node,int p){
up[node][0].first=p; depth[node]=depth[p]+1;
for(int i=1;i<20;i++){
up[node][i].first=up[up[node][i-1].first][i-1].first;
up[node][i].second=max(up[node][i-1].second,up[up[node][i-1].first][i-1].second);
}
for(auto i:adj[node]){
if(p!=i.first){
up[i.first][0].second=node;
dfs(i.first,node);
good[node]|=good[i.first];
}
}
}
pair<int,int> lca(int a,int b){
if(depth[a]<depth[b])swap(a,b);
int mx=-1;
for(int i=19;i>=0;i--){
if(depth[up[a][i].first]>=depth[b]){
mx=max(mx,up[a][i].second);
a=up[a][i].first;
}
}
if(a==b)return {a,mx};
for(int i=19;i>=0;i--){
if(up[a][i]!=up[b][i]){
mx=max({mx,up[a][i].second,up[b][i].second});
a=up[a][i].first;
b=up[b][i].first;
}
}
mx=max({mx,up[a][0].second,up[b][0].second});
return {up[a][0].first,mx};
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
on=n+1;
for(int i=1;i<=n;i++){
par[i].p=i;
}
for(int i=0;i<m;i++)e.pb({W[i],U[i],V[i]});
sort(e.begin(),e.end());
for(int i=0;i<m;i++){
deg[e[i].u]++; deg[e[i].v]++;
if(deg[e[i].u]==3){
par[find(e[i].u)].deg3=1;
adj[find(e[i].u)].pb({on,-1}); good[on]=1;
adj[on++].pb({find(e[i].u),-1});
}
if(deg[e[i].v]==3){
par[find(e[i].v)].deg3=1; good[on]=1;
adj[find(e[i].v)].pb({on,-1});
adj[on++].pb({find(e[i].v),-1});
}
merge(e[i].u,e[i].v,e[i].w);
}
}
int getMinimumFuelCapacity(int x, int y) {
pair<int,int> p=lca(x,y);
for(int i=19;i>=0;i--){
if(!good[up[p.first][i].first]){
p.second=max(p.second,up[p.first][i].second);
p.first=up[p.first][i].first;
}
}
return (p.second>1e9?-1:p.second);
}
