#include "bits/stdc++.h"
#include "swap.h"
// #include "grader.cpp"
using namespace std;
#define ff first
#define ss second
const int N = 6e5 + 5;
int p[N], a[N], c[N], h[N], par[N], sp[N][35];
pair <int, int> r[N];
vector <int> v[N];
int fnd(int x) {
if(p[x] == x) return x;
return p[x] = fnd(p[x]);
}
void dfs(int x, int y) {
h[x] = h[y] + 1;
par[x] = y;
for(auto i : v[x]) {
dfs(i, x);
}
}
int lca(int x, int y) {
if(h[x] < h[y]) swap(x, y);
for(int i = 29; i >= 0; i--) {
if(h[sp[x][i]] >= h[y]) x = sp[x][i];
}
if(x == y) return x;
for(int i = 29; i >= 0; i--) {
if(sp[x][i] != sp[y][i]) x = sp[x][i], y = sp[y][i];
}
return par[x];
}
void init(int n, int m, vector<int> U1, vector<int> U2, vector<int> W) {
vector <pair <int, pair <int, int>>> v1;
for(int i = 0; i < m; i++) {
v1.push_back({W[i], {U1[i]+1, U2[i]+1}});
}
sort(v1.begin(), v1.end());
for(int i = 0; i <= 2 * (n + m); i++) {
p[i] = i;
r[i] = {i, i};
}
int u3 = n;
for(auto [w, u] : v1) {
auto [u1, u2] = u;
u1 = fnd(u1), u2 = fnd(u2);
u3++;
p[u1] = p[u2] = u3;
c[u3] = w;
if(u1 != u2) {
if(a[u1] or a[u2]) a[u3] = true;
else {
if((u.ff == r[u1].ff or u.ff == r[u1].ss) and (u.ss == r[u2].ff or u.ss == r[u2].ss)) {
if(u.ff == r[u1].ff) r[u3].ff = r[u1].ss;
else r[u3].ff = r[u1].ff;
if(u.ss == r[u2].ff) r[u3].ss = r[u2].ss;
else r[u3].ss = r[u2].ff;
}
else a[u3] = true;
}
v[u3].push_back(u1);
v[u3].push_back(u2);
}
else {
a[u3] = true;
v[u3].push_back(u1);
}
}
dfs(u3, 0);
for(int i = 0; i <= u3; i++) {
sp[i][0] = par[i];
}
for(int j = 1; j < 30; j++) {
for(int i = 0; i <= u3; i++) {
sp[i][j] = sp[sp[i][j-1]][j-1];
}
}
a[0] = 1;
c[0] = -1;
return;
}
int getMinimumFuelCapacity(int x, int y) {
int z = lca(x+1, y+1);
if(a[z]) return c[z];
for(int i = 29; i >= 0; i--) {
if(!a[sp[z][i]]) z = sp[z][i];
}
return c[par[z]];
}
