#include<bits/stdc++.h>
// #include "swap.h"
using namespace std;
#define ll long long
const int maxn=1e5+5,sqr=447;
int n,m,f=0;
vector<array<int,3>>edges;
int par[maxn][sqr+5],sz[maxn][sqr+5];
unsigned char cnt[maxn][sqr+5];
bitset<sqr+5>good[maxn];
int dsu(int x,int sq){
if(par[x][sq]==x) return x;
return par[x][sq]=dsu(par[x][sq],sq);
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N,m=M;
for(int i=0;i<m;i++) edges.push_back({W[i],V[i],U[i]});
sort(edges.begin(),edges.end());
for(int i=0;i<n;i++) par[i][0]=i,sz[i][0]=1,good[i][0]=cnt[i][0]=0;
for(int i=1;(i-1)*sqr<m;i++){
if(i) for(int j=0;j<n;j++) par[j][i]=par[j][i-1],sz[j][i]=sz[j][i-1],good[j][i]=good[j][i-1],cnt[j][i]=cnt[j][i-1];
for(int j=(i-1)*sqr;j<i*sqr&&j<m;j++){
auto[w,a,b]=edges[j];
int a1=a,b1=b;
a=dsu(a,i);
b=dsu(b,i);
if(a==b){
good[a][i]=1;
continue;
}
if(sz[a][i]<sz[b][i]) swap(a,b);
if(cnt[a1][i]<3) cnt[a1][i]++;
if(cnt[b1][i]<3) cnt[b1][i]++;
if(cnt[a1][i]==3) good[a][i]=1;
if(cnt[b1][i]==3) good[b][i]=1;
sz[a][i]+=sz[b][i];
par[b][i]=a;
if(good[b][i]) good[a][i]=1;
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(dsu(X,m/sqr+1)!=dsu(Y,m/sqr+1)||good[dsu(X,m/sqr+1)][m/sqr+1]==0) return -1;
int last=0;
for(int i=1;(i-1)*sqr<m;i++){
if(dsu(X,i)==dsu(Y,i)&&good[dsu(X,i)][i]==1){
last=i-1;
break;
}
}
int ans=0;
vector<array<int,5>>nodes;
for(int j=last*sqr;;j++){
auto[w,a,b]=edges[j];
nodes.push_back({a,par[a][last],sz[a][last],good[a][last],cnt[a][last]});
nodes.push_back({b,par[b][last],sz[b][last],good[b][last],cnt[b][last]});
int a1=a,b1=b;
a=dsu(a,last);
b=dsu(b,last);
if(a==b){
good[a][last]=1;
if(dsu(X,last)==dsu(Y,last)&&good[dsu(X,last)][last]==1){
ans=w;
break;
}
continue;
}
if(sz[a][last]<sz[b][last]) swap(a,b);
if(cnt[a1][last]<3) cnt[a1][last]++;
if(cnt[b1][last]<3) cnt[b1][last]++;
if(cnt[a1][last]==3) good[a][last]=1;
if(cnt[b1][last]==3) good[b][last]=1;
sz[a][last]+=sz[b][last];
par[b][last]=a;
if(good[b][last]) good[a][last]=1;
if(dsu(X,last)==dsu(Y,last)&&good[dsu(X,last)][last]==1){
ans=w;
break;
}
}
reverse(nodes.begin(),nodes.end());
for(auto [id,parr,szz,goo,cn]:nodes) par[id][last]=parr,sz[id][last]=szz,good[id][last]=goo,cnt[id][last]=cn;
nodes.clear();
nodes.shrink_to_fit();
return ans;
}
