#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "swap.h"
int n,m;
int val=0;
vector<pair<int,pair<int,int>>> ed;
int par[100001];
int ss[100001];
int tt[100001];
int dd[100001];
multiset<int> xx[100001];
vector<int> comp[100001];
int ans[100001];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
void upd(int x,int y){
int stt=0;
if(ss[x]>tt[x]-1){
stt=1;
}
auto ee=xx[x].end();
ee--;
if(*ee>=3){
stt=1;
}
if(stt){
for(auto j:comp[x]){
if(ans[j]==-1){
ans[j]=y;
}
}
}
}
void init(int nn, int mm,vector<int> aa,vector<int> bb,vector<int> cc) {
m=mm;
n=nn;
for(int i=0;i<m;i++){
ed.pb({cc[i],{aa[i],bb[i]}});
}
sort(ed.begin(),ed.end());
for(int i=0;i<n;i++){
par[i]=i;
ss[i]=0;
dd[i]=0;
xx[i].clear();
tt[i]=1;
xx[i].insert(0);
ans[i]=-1;
comp[i].pb(i);
}
for(auto j:ed){
int x=find(j.b.a);
int y=find(j.b.b);
if(x==y){
ss[x]+=1;
auto jj=xx[x].find(dd[j.b.a]);
xx[x].erase(jj);
dd[j.b.a]+=1;
xx[x].insert(dd[j.b.a]);
jj=xx[x].find(dd[j.b.b]);
xx[x].erase(jj);
dd[j.b.b]+=1;
xx[x].insert(dd[j.b.b]);
if(ans[x]==-1){
upd(x,j.a);
}
}
else{
if(xx[x].size()<xx[y].size()){
swap(x,y);
}
par[y]=x;
for(auto jj:xx[y]){
xx[x].insert(jj);
}
for(auto jj:comp[y]){
comp[x].pb(jj);
if(ans[x]!=-1 and ans[jj]==-1){
ans[jj]=j.a;
}
}
xx[y].clear();
ss[x]+=ss[y]+1;
tt[x]+=tt[y];
auto jj=xx[x].find(dd[j.b.a]);
xx[x].erase(jj);
dd[j.b.a]+=1;
xx[x].insert(dd[j.b.a]);
jj=xx[x].find(dd[j.b.b]);
xx[x].erase(jj);
dd[j.b.b]+=1;
xx[x].insert(dd[j.b.b]);
if(ans[x]==-1){
upd(x,j.a);
}
}
}
/*for(int i=0;i<n;i++){
cout<<ans[i]<<":";
}
cout<<endl;*/
}
/*vector<int> adj[100001];
int vis[100001];
int st=1;
void dfs(int no,int par=-1){
vis[no]=1;
if(adj[no].size()>2){
st=0;
}
for(auto j:adj[no]){
if(j==par){
continue;
}
if(vis[j]==0){
dfs(j,no);
}
else{
st=0;
}
}
}*/
int getMinimumFuelCapacity(int aa, int bb) {
if(ans[aa]==-1 or ans[bb]==-1){
return -1;
}
int tot=max(ans[aa],ans[bb]);
for(int i=0;i<n;i++){
par[i]=i;
ss[i]=0;
dd[i]=0;
xx[i].clear();
tt[i]=1;
xx[i].insert(0);
comp[i].clear();
comp[i].pb(i);
}
for(auto j:ed){
int x=find(j.b.a);
int y=find(j.b.b);
if(x==y){
ss[x]+=1;
auto jj=xx[x].find(dd[j.b.a]);
xx[x].erase(jj);
dd[j.b.a]+=1;
xx[x].insert(dd[j.b.a]);
jj=xx[x].find(dd[j.b.b]);
xx[x].erase(jj);
dd[j.b.b]+=1;
xx[x].insert(dd[j.b.b]);
}
else{
if(xx[x].size()<xx[y].size()){
swap(x,y);
}
par[y]=x;
for(auto jj:xx[y]){
xx[x].insert(jj);
}
for(auto jj:comp[y]){
comp[x].pb(jj);
}
comp[y].clear();
xx[y].clear();
ss[x]+=ss[y]+1;
tt[x]+=tt[y];
auto jj=xx[x].find(dd[j.b.a]);
xx[x].erase(jj);
dd[j.b.a]+=1;
xx[x].insert(dd[j.b.a]);
jj=xx[x].find(dd[j.b.b]);
xx[x].erase(jj);
dd[j.b.b]+=1;
xx[x].insert(dd[j.b.b]);
}
if(find(aa)==find(bb)){
return max(tot,j.a);
}
}
return -1;
//return ac;
}
