#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#include "swap.h"
namespace{
const int maxn = 3e5 + 5;
const int INF = 1e9 + 7;
struct DSU{
vector<int> par, siz;
int n;
DSU(){}
DSU(int _n) : n(_n){
par.resize(n);
siz.resize(n, 1);
iota(par.begin(), par.end(), 0);
}
int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);}
void unite(int x, int y){
x = root(x), y = root(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
par[x] = y, siz[y] += siz[x];
}
} dsu;
struct edge{
int u, v, w;
edge(){}
edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w){}
bool operator < (const edge& other) const{
return w < other.w;
}
};
int par[maxn], w[maxn], k[maxn], dep[maxn], succ[maxn][19], mn[maxn], deg[maxn];
vector<int> adj[maxn];
}
void dfs(int pos, int prev, int nd){
if(k[pos]) nd = w[pos];
mn[pos] = nd;
succ[pos][0] = prev;
for(int i = 1; i < 19; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
for(auto x : adj[pos]){
dep[x] = dep[pos] + 1;
dfs(x, pos, nd);
}
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W){
dsu = DSU(n);
vector<edge> e;
for(int i = 0; i < m; i++) e.pb(edge(U[i], V[i], W[i]));
sort(e.begin(), e.end());
vector<int> b(n);
iota(b.begin(), b.end(), 0);
int id = n;
for(auto [u, v, wg] : e){
deg[u] ++, deg[v] ++;
int ok = (deg[u] > 2 || deg[v] > 2);
u = dsu.root(u), v = dsu.root(v);
if(u == v){
int x = b[u];
if(k[x]) continue;
int nw = id++;
adj[nw].pb(x);
par[x] = nw;
w[nw] = wg;
k[nw] = 1;
b[u] = nw;
}
else{
dsu.unite(u, v);
int nw = id++;
w[nw] = wg, k[nw] = k[b[u]] | k[b[v]] | ok;
par[b[u]] = nw, par[b[v]] = nw;
adj[nw].pb(b[u]), adj[nw].pb(b[v]);
b[u] = nw, b[v] = nw;
}
}
dfs(id - 1, id - 1, INF);
}
int lift(int x, int steps){
for(int i = 18; i >= 0; i--){
if(steps & (1 << i)) x = succ[x][i];
}
return x;
}
int find_lca(int x, int y){
if(dep[x] > dep[y]) swap(x, y);
y = lift(y, dep[y] - dep[x]);
if(x == y) return x;
for(int i = 18; i >= 0; i--){
if(succ[x][i] != succ[y][i]) x = succ[x][i], y = succ[y][i];
}
return succ[x][0];
}
int getMinimumFuelCapacity(int x, int y){
int lca = find_lca(x, y);
if(mn[lca] == INF) mn[lca] = -1;
return mn[lca];
}
