#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=1e5, mxM=2e5;
int n, m, p[mxN], anc[2*mxN][18], first[2*mxN], n2, d[2*mxN], ans[2*mxN];
ar<int, 3> e[mxM];
vector<int> adj[mxN];
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
void dfs(int u) {
for (int v : adj[u]) {
d[v]=d[u]+1;
dfs(v);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N, m=M, n2=n;
for (int i=0; i<m; ++i)
e[i]={W[i], U[i], V[i]};
sort(e, e+m);
iota(p, p+2*n, 0);
memset(anc, -1, sizeof(anc));
memset(first, -1, sizeof(first));
for (int i=0; i<m; ++i) {
int u=find(e[i][1]), v=find(e[i][2]);
if (u!=v) {
p[u]=p[v]=anc[u][0]=anc[v][0]=n2;
first[n2]=first[v]==-1||first[u]!=-1&&first[u]<first[v]?first[u]:first[v];
adj[n2].push_back(u);
adj[n2].push_back(v);
ans[n2]=max(e[i][0], first[n2]);
++n2;
} else if (first[u]==-1) {
first[u]=e[i][0];
ans[u]=max(ans[u], first[u]);
}
}
for (int j=1; j<18; ++j)
for (int i=0; i<n2; ++i)
anc[i][j]=anc[i][j-1]^-1?anc[anc[i][j-1]][j-1]:-1;
assert(n2==2*n-1);
dfs(n2-1);
}
int lca(int u, int v) {
if (d[u]>d[v])
swap(u, v);
for (int i=17; ~i; --i)
if (d[v]-(1<<i)>=d[u])
v=anc[v][i];
if (u==v)
return u;
for (int i=17; ~i; --i)
if (anc[u][i]!=anc[v][i])
u=anc[u][i], v=anc[v][i];
return anc[u][0];
}
int getMinimumFuelCapacity(int u, int v) {
int uv=lca(u, v);
return first[uv]^-1?ans[uv]:-1;
}
