#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100'000;
const int E = 200'000;
const int M = 18;
const int INF = 1'000'000'100;
int n, m, deg[N + 10], h[N + 10];
int x[E + 10], y[E + 10], w[E + 10];
int dp[N + 10][M + 3], sp[N + 10][M + 3];
int par[N + 10], mark3[N + 10], markC[N + 10];
int val3[N + 10], valC[N + 10];
vector<pair<int, int>> adj[N + 10], edge;
vector<int> cmp[N + 10];
void readInput(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (int i = 1; i <= m; i++) {
x[i] = U[i - 1] + 1;
y[i] = V[i - 1] + 1;
w[i] = W[i - 1];
edge.push_back({w[i], i});
}
}
int getPar(int u) {
return (par[u] < 0? u: (par[u] = getPar(par[u])));
}
void addMark3(int u, int w) {
u = getPar(u);
if (mark3[u])
return;
mark3[u] = true;
for (auto v: cmp[u])
val3[v] = min(val3[v], w);
}
void addMarkC(int u, int w) {
u = getPar(u);
if (markC[u])
return;
markC[u] = true;
for (auto v: cmp[u])
valC[v] = min(valC[v], w);
}
bool merg(int u, int v, int w) {
deg[u]++;
deg[v]++;
if (deg[u] >= 3 || deg[v] >= 3) {
addMark3(u, w);
addMark3(v, w);
}
if ((u = getPar(u)) == (v = getPar(v))) {
addMarkC(u, w);
return false;
}
if (par[v] < par[u])
swap(u, v);
if (mark3[u] != mark3[v])
addMark3((mark3[u]? v: u), w);
if (markC[u] != markC[v])
addMarkC((markC[u]? v: u), w);
while (cmp[v].size()) {
cmp[u].push_back(cmp[v].back());
cmp[v].pop_back();
}
cmp[v].shrink_to_fit();
par[u] += par[v];
par[v] = u;
return true;
}
void addEdge(int u, int v,int w) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
void checkEdges() {
for (int i = 1; i <= n; i++) {
cmp[i].push_back(i);
par[i] = -1;
val3[i] = valC[i] = INF;
}
sort(edge.begin(), edge.end());
for (auto [weight, e]: edge)
if (merg(x[e], y[e], w[e]))
addEdge(x[e], y[e], w[e]);
}
void dfs(int u = 1, int par = 0, int wUp = 0) {
h[u] = h[par] + 1;
dp[u][0] = par;
sp[u][0] = wUp;
for (int j = 1; j <= M && dp[u][j - 1]; j++) {
dp[u][j] = dp[dp[u][j - 1]][j - 1];
sp[u][j] = max(sp[u][j - 1], sp[dp[u][j - 1]][j - 1]);
}
for (auto [v, w]: adj[u])
if (v != par)
dfs(v, u, w);
}
int maxPath(int u, int v) {
if (h[u] < h[v])
swap(u, v);
int res = 0;
for (int j = M; j >= 0; j--)
if (h[u] - h[v] >= (1 << j)) {
res = max(res, sp[u][j]);
u = dp[u][j];
}
if (u == v)
return res;
for (int j = M; j >= 0; j--)
if (dp[u][j] != dp[v][j]) {
res = max({res, sp[u][j], sp[v][j]});
u = dp[u][j];
v = dp[v][j];
}
return max({res, sp[u][0], sp[v][0]});
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
readInput(N, M, U, V, W);
checkEdges();
dfs();
}
int query(int u, int v) {
int case1 = maxPath(u, v);
int case2 = min(valC[u], valC[v]);
int case3 = min(val3[u], val3[v]);
//cout << u << ' ' << v << ": " << case1 << ' ' << case2 << ' ' << case3 << '\n';
int res = max(case1, min(case2, case3));
return (res == INF? -1: res);
}
int getMinimumFuelCapacity(int X, int Y) {
return query(X + 1, Y + 1);
}
/*int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> u(m), v(m), w(m);
for (int i = 0; i < m; i++)
cin >> u[i] >> v[i] >> w[i];
init(n, m, u, v, w);
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << getMinimumFuelCapacity(x, y) << '\n';
}
cout.flush();
return 0;
}*/
