// Starcraft 2 enjoyer //
#include "swap.h"
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e6 + 5;
const int M = 1e6 + 5;
const int K = 20;
const int LG = 21;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;
int n, m, parent[N], sz[N], cid, val[N], binlift[LG][N], depth[N], l[N], r[N], mn[N]; // val1 is for
vector<array<int, 3>> edges;
vector<int> adj[N];
int getParent(int x)
{
return parent[x] == x ? x : parent[x] = getParent(parent[x]);
}
void update(int a, int b, int v)
{
int ia = a, ib = b;
a = getParent(a);
b = getParent(b);
if (a != b)
{
parent[b] = cid;
parent[a] = cid;
if ((ia == l[a] || ia == r[a]) && (ib == l[b] || ib == r[b]))
{
if (l[a] == ia)
l[cid] = r[a];
else
l[cid] = l[a];
if (l[b] == ib)
r[cid] = r[b];
else
r[cid] = l[b];
}
else
{
l[cid] = -1;
r[cid] = -1;
}
// cout << cid << " " << a << " " << b << "\n";
sz[cid] = sz[a] + sz[b];
parent[a] = cid;
parent[b] = cid;
adj[cid].push_back(b);
adj[cid].push_back(a);
if (l[cid] == -1)
val[cid] = v;
else
val[cid] = -1;
cid++;
}
else
{
l[a] = r[a] = -1;
// cout << a << "\n";
if (val[a] == -1)
val[a] = v;
}
}
bool chkConnect(int a, int b)
{
return getParent(a) == getParent(b);
}
void dfs(int c, int p)
{
if (l[c] == -1)
{
mn[c] = min(mn[c], val[c]);
if (mn[c] == -1)
mn[c] = val[c];
}
// cout << mn[c] << " " << val[c] << " " << c << "\n";
for (int i : adj[c])
{
if (i == p)
continue;
mn[i] = mn[c];
depth[i] = depth[c] + 1;
binlift[0][i] = c;
for (int x = 1; x < LG; x++)
{
binlift[x][i] = binlift[x - 1][binlift[x - 1][i]];
}
dfs(i, c);
}
}
int lca(int a, int b)
{
if (depth[a] != depth[b])
{
if (depth[a] < depth[b])
swap(a, b);
int k = depth[a] - depth[b];
for (int x = 0; x < LG; x++)
{
if (k >> x & 1)
{
a = binlift[x][a];
}
}
}
if (a == b)
return a;
for (int x = LG - 1; x >= 0; x--)
{
if (binlift[x][a] != binlift[x][b])
{
a = binlift[x][a];
b = binlift[x][b];
}
}
return binlift[0][a];
}
void init(int i, int j, vector<int> u, vector<int> v, vector<int> w)
{
n = i;
m = j;
cid = n + 1;
for (int x = 1; x <= 2 * n; x++)
{
l[x] = r[x] = x;
parent[x] = x;
sz[x] = 1;
mn[x] = -1;
val[x] = -1;
}
for (int x = 0; x < m; x++)
{
u[x]++;
v[x]++;
edges.push_back({w[x], u[x], v[x]});
}
sort(edges.begin(), edges.end());
for (auto &[w, u, v] : edges)
{
update(u, v, w);
}
dfs(cid - 1, 0);
}
int getMinimumFuelCapacity(int a, int b)
{
a++;
b++;
int i = lca(a, b);
// cout << l[i] << " " << r[i] << " " << i << "\n";
return mn[i];
}
