#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int INF = 1e9+5;
const int lg = 18;
int n;
int sp[lg][maxn];
int sp_mx[lg][maxn], sp_mn[lg][maxn];
int dep[maxn];
int in_tree[maxn];
vector<pair<int, int>> g[maxn];
vector<pair<int, pair<int, int>>> E;
int up[maxn];
int Find(int x){
return up[x] != -1 ? up[x] = Find(up[x]) : x;
}
bool Union(int a, int b){
a = Find(a);
b = Find(b);
if(a == b)return false;
up[a] = b;
return true;
}
void dfs(int x, int p){
sp_mn[0][x] = INF;
sp[0][x] = p;
for(auto v: g[x]){
if(v.first == p)continue;
dep[v.first] = dep[x] + 1;
sp_mx[0][v.first] = v.second;
dfs(v.first, x);
}
}
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]];
sp_mx[i][j] = max(sp_mx[i-1][j], sp_mx[i-1][sp[i-1][j]]);
}
sp_mn[i][j] = INF;
}
}
}
void tup_upd(int &x, int dist, int w){
for(int i = 0; i < lg; i++){
if(dist&(1<<i)){
sp_mn[i][x] = w;
x = sp[i][x];
}
}
}
void upd_path(int a, int b, int w){
if(dep[a] < dep[b])swap(a, b);
tup_upd(a, dep[a] - dep[b], w);
if(a == b)return;
for(int i = lg-1; i >= 0; i--){
if(sp[i][a] != sp[i][b]){
sp_mn[i][a] = min(sp_mn[i][a], w);
sp_mn[i][b] = min(sp_mn[i][b], w);
a = sp[i][a];
b = sp[i][b];
}
}
sp_mn[0][a] = min(sp_mn[0][a], w);
sp_mn[0][b] = min(sp_mn[0][b], w);
}
void push(){
for(int i = lg-1; i > 0; i--){
for(int j = 0; j < n; j++){
if(sp[i][j] == -1)continue;
sp_mn[i-1][j] = min(sp_mn[i-1][j], sp_mn[i][j]);
sp_mn[i-1][sp[i-1][j]] = min(sp_mn[i-1][sp[i-1][j]], sp_mn[i][j]);
}
}
}
void tup_query(int &x, int dist, int &mx, int &mn){
for(int i = 0; i < lg; i++){
if(dist&(1<<i)){
mn = min(sp_mn[i][x], mn);
mx = max(sp_mx[i][x], mx);
x = sp[i][x];
}
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
for(int i = 0; i < M; i++){
E.push_back({W[i], {U[i], V[i]}});
}
for(int i = 0; i < N; i++)up[i] = -1;
sort(E.begin(), E.end());
for(int i = 0; i < M; i++){
if(Union(E[i].second.first, E[i].second.second)){
// cout << E[i].second.first << " " << E[i].second.second << endl
g[E[i].second.first].push_back({E[i].second.second, E[i].first});
g[E[i].second.second].push_back({E[i].second.first, E[i].first});
in_tree[i] = 1;
}
}
dfs(0, -1);
build();
for(int i = 0; i < M; i++){
if(!in_tree[i])upd_path(E[i].second.first, E[i].second.second, E[i].first);
}
push();
}
int getMinimumFuelCapacity(int a, int b) {
int mx = 0, mn = INF;
if(dep[a] < dep[b])swap(a, b);
tup_query(a, dep[a] - dep[b], mx, mn);
if(a != b){
for(int i = lg-1; i >= 0; i--){
if(sp[i][a] != sp[i][b]){
mn = min(sp_mn[i][a], mn);
mn = min(sp_mn[i][b], mn);
mx = max(sp_mx[i][a], mx);
mx = min(sp_mx[i][b], mx);
a = sp[i][a];
b = sp[i][b];
}
}
mn = min(sp_mn[0][a], mn);
mn = min(sp_mn[0][b], mn);
mx = max(mx, sp_mx[0][a]);
mx = max(mx, sp_mx[0][b]);
}
if(max(mn, mx) == INF)return -1;
return max(mn, mx);
}
