#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
const int inf = 1e9;
const int mxN = 1e5 + 100;
const int mxB = 21;
vector<int> adj[mxN * 4];
vector<tuple<int, int, int>> edge;
int par[mxN * 4], ans[mxN * 4], en[mxN * 4], dep[mxN * 4], deg[mxN * 4], ok[mxN * 4], cost[mxN * 4], vis[mxN * 4];
pair<int, int> dp[mxN * 8][mxB];
vector<int> euler;
vector<pair<int, int>> baddie;
int find(int u) {
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
void dfs(int u, int p) {
euler.push_back(u);
dep[u] = dep[p] + 1;
baddie.push_back({dep[u], u});
for(auto v : adj[u]) {
dfs(v, u);
euler.push_back(u);
}
en[u] = (int) euler.size();
euler.push_back(u);
}
void calc(int u, int till) {
vis[u] = 1;
if(ok[u]) till = min(till, cost[u]);
if(ans[u] < inf) till = min(till, ans[u]);
ans[u] = till;
for(auto v : adj[u]) {
calc(v, till);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < M; ++i) edge.push_back({W[i], U[i], V[i]});
sort(edge.begin(), edge.end());
for(int i = 0; i < N * 4; ++i) {
ans[i] = inf, par[i] = i;
}
int ln = N;
for(auto [w, u, v] : edge) {
deg[u] += 1, deg[v] += 1;
int up = find(u), vp = find(v);
if(up == vp) {
ok[up] = 1;
continue;
}
cost[++N] = w;
adj[N].push_back(up);
adj[N].push_back(vp);
ok[N] = (ok[up] || ok[vp] || max(deg[u], deg[v]) >= 3);
par[up] = par[vp] = N;
}
for(int i = 2 * ln; i >= 0; --i) {
if(!dep[i]) dfs(i, 0);
}
for(int i = 0; i < (int) euler.size(); ++i) {
dp[i][0] = {dep[euler[i]], euler[i]};
}
for(int j = 1; j < mxB; ++j) {
for(int i = 0; i + (1 << j) - 1 < (int) euler.size(); ++i) {
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
sort(baddie.begin(), baddie.end(), greater<>());
for(auto [x, v] : baddie) if(!vis[v]) calc(v, inf);
}
int lca(int u, int v) {
if(en[u] > en[v]) swap(u, v);
int k = __lg(en[v] - en[u] + 1);
return min(dp[en[u]][k], dp[en[v] - (1 << k) + 1][k]).second;
}
int getMinimumFuelCapacity(int X, int Y) {
if(find(X) != find(Y)) return -1;
int res = ans[lca(X, Y)];
return res >= inf ? -1 : res;
}
