#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
int par[200005];
int lift[200005][20];
vector<int> krus[200005];
int st[200005], ed[200005];
int dsu[200005];
int ans[200005];
int deg[200005];
int timer = 0;
pair< int, pair< int, int> > edg[200005];
bool anc(int x, int y) {
return st[x] <= st[y] && ed[x] >= ed[y];
}
int lca(int x, int y) {
if(anc(x, y)) return x;
for(int i=19; i>=0; i--) {
if(lift[x][i]==-1) continue;
if(!anc(lift[x][i], y)) x = lift[x][i];
}
return lift[x][0];
}
int find(int x) {
if(dsu[x]==x) return x;
else return dsu[x] = find(dsu[x]);
}
void dfs(int x) {
st[x] = ++timer;
lift[x][0] = par[x];
for(int i=1; i<20; i++) {
if(lift[x][i-1]==-1) lift[x][i]=-1;
else lift[x][i] = lift[lift[x][i-1]][i-1];
}
for(int i:krus[x]) {
ans[i] = min(ans[i], ans[x]);
dfs(i);
}
ed[x] = ++timer;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
for(int i=0; i<M; i++) {
edg[i] = {W[i], {U[i], V[i]} };
}
sort(edg, edg+M);
for(int i=0; i<N*2; i++) dsu[i] = i, ans[i] = 2e9, deg[i] = 0;
int tmp = N;
for(int i=0; i<M; i++) {
if(find(edg[i].second.first) != find(edg[i].second.second)) {
krus[tmp].push_back(dsu[edg[i].second.first]);
krus[tmp].push_back(dsu[edg[i].second.second]);
par[dsu[edg[i].second.first]] = par[dsu[edg[i].second.second]] = tmp;
if(ans[dsu[edg[i].second.first]]<2e9 || ans[dsu[edg[i].second.second]]<2e9) ans[tmp] = edg[i].first;
dsu[dsu[edg[i].second.first]] = dsu[dsu[edg[i].second.second]] = tmp;
tmp++;
} else { // cycle
ans[find(edg[i].second.first)] = min(ans[find(edg[i].second.first)], edg[i].first);
}
deg[edg[i].second.first]++; deg[edg[i].second.second]++;
if(deg[edg[i].second.first] >= 3 || deg[edg[i].second.second] >= 3) {
ans[find(edg[i].second.first)] = min(ans[find(edg[i].second.first)], edg[i].first);
}
}
par[tmp-1] = -1;
dfs(tmp-1);
}
int getMinimumFuelCapacity(int X, int Y) {
return ans[lca(X, Y)] == 2e9 ? -1 : ans[lca(X, Y)];
}
