/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 3e5+10;
const int inf = 1e9;
int p[N+1], sw[N+1], deg[N+1], we[N+1], dep[N+1];
int par[N+1][30];
vector<int> taze[N+1];
vector<pair<int, pair<int, int>>> g;
int get(int u) {
if (p[u] != u)return p[u] = get(p[u]);
return u;
}
void build(int u, int pr) {
par[u][0] = pr;
//if (u == 4)cout << pr << nl;
for (int i = 1; i < 30; ++i) {
if ((1 << i) > dep[u])break;
par[u][i] = par[par[u][i-1]][i-1];
}
for (auto i: taze[u]) {
if (i == pr)continue;
dep[i] = dep[u] + 1;
build(i, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v])swap(u, v);
for (int i = 29; i >= 0; --i) {
if (par[u][i] == -1)continue;
if (dep[par[u][i]] >= dep[v])u = par[u][i];
}
//cout << u << " " << v << nl;
if (u == v)return u;
for (int i = 29; i >= 0; --i)
if (par[u][i] != par[v][i]) {
u = par[u][i], v = par[v][i];
}
return par[u][0];
}
void init(int n, int m, vector<int> ue, vector<int> ve, vector<int> wee) {
memset(par, -1, sizeof par);
for (int i = 0; i < m; ++i) {
g.push_back({wee[i], {ue[i], ve[i]}});
}
for (int i = 0; i <= N; ++i)
p[i] = i, sw[i] = 0, deg[i] = 0;
int add = n;
sort(all(g));
for (auto i: g) {
int w, u, v;
w = i.first, u = i.second.first, v = i.second.second;
int gt1 = get(u), gt2 = get(v);
p[gt1] = p[gt2] = add;
add += 1;
//cout << w << nl;
if (gt1 == gt2) {// cycle
sw[add-1] = 1, we[add-1] = w;
taze[add-1].push_back(gt1);
} else {
taze[add-1].push_back(gt1);
taze[add-1].push_back(gt2);
deg[u] += 1, deg[v] += 1;
if (max(deg[u], deg[v]) >= 3 || max(sw[gt1], sw[gt2]) == 1)sw[add-1] = 1;
we[add-1] = w;
}
}
build(add-1, 0);
}
int getMinimumFuelCapacity(int u, int v) {
int l = lca(u, v);
if (sw[l] == 1)return we[l];
for (int i = 29; i >= 0; --i) {
if (par[l][i] == -1)continue;
if (sw[par[l][i]] != 1)l = par[l][i];
}
l = par[l][0];
if (l == -1 || sw[l] == 0)return -1;
return we[l];
}
