#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const bool debug = 1;
const int N = 1e5 + 5;
const int L = 20;
const int inf = 2e9;
struct edge{
int u, v, w;
bool operator < (const edge &o) const {return w<o.w;}
};
int n, m;
int p[N][L], ma[N][L], tin[N], tout[N];
int sz[N], dep[N], id[N], top[N], timer;
int root[N];
int t[4*N];
vector<pair<int, int>> adj[N];
vector<edge> back_edge, all_edge;
int findroot(int x) {return root[x]==x?x:root[x]=findroot(root[x]);}
int dfs(int v=0) {
sz[v] = 1;
tin[v] = ++timer;
for (int i=1; i<L; i++) {
p[v][i] = p[p[v][i-1]][i-1];
ma[v][i] = max(ma[v][i-1], ma[p[v][i-1]][i-1]);
}
for (auto [to, w] : adj[v]) if (to!=p[v][0]) {
p[to][0] = v;
ma[to][0] = w;
dep[to] = dep[v] + 1;
sz[v] += dfs(to);
}
tout[v] = ++timer;
return sz[v];
}
bool is_anc(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
int ret = -1;
for (int i=L-1; i>=0; i--) if (!is_anc(p[u][i], v)) {
ret = max(ret, ma[u][i]); u = p[u][i];
}
for (int i=L-1; i>=0; i--) if (!is_anc(p[v][i], u)) {
ret = max(ret, ma[v][i]); v = p[v][i];
}
if (!is_anc(u, v)) ret = max(ret, ma[u][0]);
if (!is_anc(v, u)) ret = max(ret, ma[v][0]);
return ret;
}
void hld(int v=0, int tp=0) {
id[v] = ++timer;
top[v] = tp;
int h_chi = -1, h_sz = -1;
for (auto [to, w] : adj[v]) if (to!=p[v][0] && h_sz<sz[to]) h_sz = sz[to], h_chi = to;
if (h_chi == -1) return;
hld(h_chi, tp);
for (auto [to, w] : adj[v]) if(to!=p[v][0] && to!=h_chi) hld(to, to);
}
void upd_seg(int l, int r, int val, int v=1, int tl=1, int tr=n) {
if (tl > r || tr < l) return;
if (l <= tl && tr <= r) {
if (t[v] == -1) t[v] = val;
return;
}
int tm = (tl+tr)/2;
upd_seg(l, r, val, 2*v, tl, tm);
upd_seg(l, r, val, 2*v+1, tm+1, tr);
}
int query_seg(int l, int r, int v=1, int tl=1, int tr=n) {
if (tl > r || tr < l) return -1;
if (l <= tl && tr <= r) return t[v];
int tm = (tl+tr)/2;
return max(t[v], max(query_seg(l, r, 2*v, tl, tm), query_seg(l, r, 2*v+1, tm+1, tr)));
}
void upd_path(int u, int v, int val) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
upd_seg(id[top[u]], id[u], val);
u = p[top[u]][0];
}
if (u != v) {
if (dep[u] > dep[v]) swap(u, v);
upd_seg(id[u]+1, id[v], val);
}
}
int query_path(int u, int v) {
int ret = -1;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = max(ret, query_seg(id[top[u]], id[u]));
u = p[top[u]][0];
}
if (u != v) {
if (dep[u] > dep[v]) swap(u, v);
ret = max(ret, query_seg(id[u]+1, id[v]));
}
return ret;
}
void init(int NN, int MM, vector<int> U, vector<int> V, vector<int> W)
{
n = NN, m = MM;
for (int i=0; i<m; i++) all_edge.push_back({U[i], V[i], W[i]});
sort(all_edge.begin(), all_edge.end());
for (int i=0; i<n; i++) root[i] = i;
for (auto [u, v, w] : all_edge) {
int ru = findroot(u), rv = findroot(v);
if (ru == rv) back_edge.push_back({u, v, w});
else root[rv] = ru, adj[u].push_back({v, w}), adj[v].push_back({u, w});
}
dfs();
timer = 0;
hld();
fill_n(t, 4*N, -1);
for (auto [u, v, w] : back_edge) upd_path(u, v, w);
}
int getMinimumFuelCapacity(int X, int Y)
{
int res = query_path(X, Y);
if (res == -1) return -1;
return max(res, lca(X, Y));
}
