#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
const int MOD = 1e9+7; // 998244353;
vctr<pii> adj[100005];
int d[100005];
int pw[100005];
int pa[100005];
int deg[100005];
int nxt[100005];
struct DSU {
void init(int n) {
fill(pa+1,pa+n+1,-1);
fill(nxt+1,nxt+n+1,2e9);
}
int root(int x) {
return pa[x] < 0 ? x : root(pa[x]);
}
int unite(int x, int y, int w) {
int px = root(x);
int py = root(y);
if (pa[px] > pa[py])swap(px,py),swap(x,y);
if (++deg[x] > 2) {
amin(nxt[px],w);
}
if (++deg[y] > 2) {
amin(nxt[px],w);
}
if (px == py) {
amin(nxt[px],w);
return -1;
}
pa[px] += pa[py];
pa[py] = px;
adj[px].eb(py,w);
amin(nxt[px],max(w,nxt[py]));
pw[py] = w;
return px;
}
} dsu;
void dfs(int node, int fa) {
d[node] = d[fa]+1;
for (auto [it,w] : adj[node]) {
if (it == fa)continue;
// cout << node << "->" << it << '\n';
amin(nxt[it],nxt[node]);
dfs(it,node);
}
return;
}
void init(int n, int m, vctr<int> U, vctr<int> V, vctr<int> W) {
vctr<tiii> edges;
for (int i = 0; i < m; ++i) {
edges.eb(W[i],U[i],V[i]);
}
sort(all(edges));
dsu.init(n);
for (auto [w,u,v] : edges) {
++u; ++v;
// brick(w);brick(u);dbg(v);
dsu.unite(u,v,w);
}
dfs(dsu.root(1),0);
return;
}
int getMinimumFuelCapacity(int x, int y) {
++x; ++y;
int xi = x, yi = y;
if (d[xi] > d[yi])swap(xi,yi), swap(x,y);
int prv = 0;
while (d[xi] < d[yi])prv = yi, yi = pa[yi];
if (xi == yi) {
int ans = max(nxt[xi],pw[prv]);
if (ans == (int)2e9)ans = -1;
return ans;
}
while (pa[xi] != pa[yi])xi = pa[xi], yi = pa[yi];
int ans = max(nxt[pa[xi]],max(pw[xi],pw[yi]));
if (ans == (int)2e9)ans = -1;
return ans;
}
