#include <bits/stdc++.h>
#include "swap.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e5+10;
const int inf = 1e9+10;
int n;
int mn3[maxn];
int ans[maxn];
int D[maxn], par[maxn];
bool mark[maxn];
vector<pii> grafo[maxn];
struct Edge
{
int u, v, w;
} edge[maxn];
struct DSU
{
int pai[maxn], peso[maxn], nivel[maxn], val[maxn], tt[maxn];
void init(int n)
{
for (int i = 1; i <= n; i++)
{
pai[i] = i, peso[i] = 1, nivel[i] = 0;
if (grafo[i].size() >= 3) val[i] = mn3[i];
else val[i] = inf;
}
}
int Find(int x)
{
if (pai[x] == x) return x;
return Find(pai[x]);
}
void Join(int x, int y, int t)
{
x = Find(x), y = Find(y);
if (x == y) return;
if (peso[x] < peso[y]) swap(x, y);
pai[y] = x, peso[x] += peso[y], tt[y] = t;
}
void dfs(int u)
{
if (u == Find(u))
{
nivel[u] = 1;
return;
}
if (!nivel[pai[u]]) dfs(pai[u]);
nivel[u] = nivel[pai[u]]+1;
}
void upd(int u)
{
int v = u;
int mx = 0;
while (true)
{
val[v] = min(val[v], max(mn3[u], mx));
if (pai[v] == v) return;
mx = max(mx, tt[v]);
v = pai[v];
}
}
int get(int u)
{
int v = u, ans = inf, mx = 0;
while (true)
{
ans = min(ans, max(mx, val[v]));
if (v == pai[v]) return ans;
mx = max(mx, tt[v]);
v = pai[v];
}
}
int get_mx(int u, int v)
{
int ans = 0;
while (u != v)
{
if (nivel[u] > nivel[v])
{
ans = max(ans, tt[u]);
u = pai[u];
}
else
{
ans = max(ans, tt[v]);
v = pai[v];
}
}
return ans;
}
} dsu;
void init(int N, int m, vector<int> U, vector<int> V, vector<int> W)
{
n = N;
for (int i = 0; i < m; i++)
{
grafo[U[i]+1].push_back({V[i]+1, W[i]});
grafo[V[i]+1].push_back({U[i]+1, W[i]});
edge[i+1] = {U[i]+1, V[i]+1, W[i]};
}
sort(edge+1, edge+m+1, [&] (Edge a, Edge b) {return a.w < b.w;});
for (int i = 1; i <= n; i++)
{
sort(grafo[i].begin(), grafo[i].end(), [&] (pii a, pii b) {return a.ss < b.ss;});
if (grafo[i].size() <= 2) mn3[i] = inf;
else mn3[i] = grafo[i][2].ss;
}
dsu.init(n);
for (int i = 1; i <= m; i++)
{
if (dsu.Find(edge[i].u) == dsu.Find(edge[i].v))
{
mn3[edge[i].u] = min(mn3[edge[i].u], edge[i].w);
mn3[edge[i].v] = min(mn3[edge[i].v], edge[i].w);
}
dsu.Join(edge[i].u, edge[i].v, edge[i].w);
}
for (int i = 1; i <= n; i++)
{
if (mn3[i] != inf)
dsu.upd(i);
if (!dsu.nivel[i])
dsu.dfs(i);
}
}
int getMinimumFuelCapacity(int u, int v)
{
u++, v++;
if (u == v) return -1;
if (min(dsu.get(u), dsu.get(v)) == inf) return -1;
return max(min(dsu.get(u), dsu.get(v)), dsu.get_mx(u, v));
}
