#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const int INF = 1e9+5;
const int lg = 20;
int n, m;
int Wmax;
int sp[lg][maxn];
vector<int> g[maxn];
vector<pair<int, pair<int, int>>> E;
int up[maxn], L[maxn], R[maxn], dep[maxn], dp[maxn];
int Find(int x){
return up[x] != -1 ? up[x] = Find(up[x]) : x;
}
void Union(int a, int b, int w){
int ra = Find(a);
int rb = Find(b);
if(ra != rb){
if(L[ra] == -1 || L[rb] == -1){
L[n] = R[n] = -1;
dp[n] = w;
}
else {
if(a != L[ra])swap(L[ra], R[ra]);
if(b != L[rb])swap(L[rb], R[rb]);
if(a == L[ra] && b == L[rb]){
L[n] = R[ra];
R[n] = R[rb];
dp[n] = INF;
}
else {
L[n] = R[n] = -1;
dp[n] = w;
}
}
g[n].push_back(ra);
g[n].push_back(rb);
up[ra] = n;
up[rb] = n;
}
else {
g[n].push_back(ra);
L[n] = R[n] = -1;
up[ra] = n;
dp[n] = w;
}
up[n] = -1;
n++;
}
void dfs(int x){
for(auto v: g[x]){
sp[0][v] = x;
dep[v] = dep[x] + 1;
dp[v] = min(dp[v], dp[x]);
dfs(v);
}
}
void build(){
for(int i = 1; i < lg; i++){
for(int j = 0; j < n; j++){
if(sp[i-1][j] == -1)sp[i][j] = -1;
else sp[i][j] = sp[i-1][sp[i-1][j]];
}
}
}
void tup(int &x, int dist){
for(int i = 0; i < lg; i++){
if(dist&(1<<i))x = sp[i][x];
}
}
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 < n; i++){
up[i] = -1;
dp[i] = INF;
L[i] = R[i] = i;
}
for(int i = 0; i < m; i++){
E.push_back({W[i], {U[i], V[i]}});
}
sort(E.begin(), E.end());
for(auto v: E)Union(v.second.first, v.second.second, v.first);
sp[0][n-1] = -1;
dfs(n-1);
build();
}
int getMinimumFuelCapacity(int a, int b) {
if(dep[a] < dep[b])swap(a, b);
tup(a, dep[a] - dep[b]);
for(int i = lg-1; i >= 0; i--){
if(sp[i][a] != sp[i][b]){
a = sp[i][a];
b = sp[i][b];
}
}
a = sp[0][a];
if(dp[a] == INF)return -1;
return dp[a];
}
