#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 make(int a,int b,int cur){
adj[a].pb({on,cur});
if(b>=0)adj[b].pb({on,cur});
adj[on].pb({a,cur});
if(b>=0)adj[on].pb({b,cur});
par[a].p=on;
if(b>=0)par[b].p=on;
//cout<<a<<' '<<b<<' '<<on<<endl;
par[on]=par[a];
if(b>=0)par[on].deg3=(par[a].deg3|par[b].deg3); par[on].cycle=(par[a].cycle|par[b].cycle);
par[on].p=on;
if(par[on].cycle || par[on].deg3)good[on]=1;
on++;
}
void merge(int a,int b,int cur){
deg[a]++; deg[b]++;
if(deg[a]>=3 && !par[find(a)].deg3){
a=find(a);
make(a,-1,cur);
}
if(deg[b]>=3 && !par[find(b)].deg3){
b=find(b);
make(b,-1,cur);
}
a=find(a); b=find(b);
if(a==b){
par[a].cycle=1;
make(a,-1,cur);
return;
}
make(a,b,cur);
}
void dfs(int node,int p){
// cout<<node<<' '<<p<<' '<<up[node][0].second<<" yes "<<good[node]<<endl;
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=i.second;
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++){
e[i].u++; e[i].v++;
merge(e[i].u,e[i].v,e[i].w);
}
dfs(on-1,0);
}
int getMinimumFuelCapacity(int x, int y) {
good[0]=1;
x++; y++;
pair<int,int> p=lca(x,y);
// cout<<p.first<<' '<<p.second<<endl;
for(int i=19;i>=0;i--){
if(!good[up[p.first][i].first]){
// cout<<i<<' '<<p.first<<" "<<up[p.first][i].second<<endl;
p.second=max(p.second,up[p.first][i].second);
p.first=up[p.first][i].first;
}
}
if(!good[p.first]){
p.second=max(p.second,up[p.first][0].second);
p.first=up[p.first][0].first;
}
if(p.first==0 || !good[p.first])return -1;
return p.second;
}
