#include <bits/stdc++.h>
//#include "swap.h"
using namespace std;
const int maxN = 3e5 + 5;
bool good[maxN], is_true[20][maxN], status[maxN];
int par[20][maxN], mx[20][maxN], weight[maxN], curr[maxN], deg[maxN], depth[maxN];
int DSUpar[maxN], DSUsz[maxN];
vector<int> adj[maxN];
int find_set(int u) {
return (DSUpar[u] == u) ? u : DSUpar[u] = find_set(DSUpar[u]);
}
void union_set(int u, int v, int w, int node) {
int A = find_set(u), B = find_set(v);
if (A == B) {
adj[node].push_back(curr[A]);
curr[A] = node;
good[A] = true;
weight[node] = w;
status[node] = true;
return ;
}
if (DSUsz[A] < DSUsz[B]) swap(A, B);
DSUpar[B] = A;
DSUsz[A] += DSUsz[B];
adj[node].push_back(curr[A]);
adj[node].push_back(curr[B]);
curr[A] = node;
if (good[A] || good[B] || ++deg[u] >= 3 || ++deg[v] > 3) good[A] = true;
status[node] = good[A];
weight[node] = w;
}
struct Edg {
int u, v, w;
bool operator < (const Edg& rhs) const {
return w < rhs.w;
}
} edge[maxN];
void dfs(int u) {
for (auto v: adj[u]) {
par[0][v] = u;
mx[0][v] = weight[u];
is_true[0][v] = status[u];
depth[v] = depth[u] + 1;
dfs(v);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < M; i++)
edge[i + 1] = {U[i] + 1, V[i] + 1, W[i]};
sort(edge + 1, edge + M + 1);
for (int i = 1; i <= N + M; i++) {
DSUpar[i] = i;
DSUsz[i] = 1;
curr[i] = i;
}
for (int i = 1; i <= M; i++) {
auto [u, v, w] = edge[i];
union_set(u, v, w, N + i);
}
/*cout << "Init\n";
for (int i = N + 1; i <= N + M; i++) {
cout << "Node " << i << '\n';
cout << weight[i] << ' ' << status[i] << '\n';
cout << "Adj ";
for (auto v: adj[i])
cout << v << ' ';
cout << '\n';
}*/
depth[N + M] = 1;
dfs(N + M);
//for (int i = 1; i <= N + M; i++)
//cout << par[0][i] << ' ' << mx[0][i] << ' ' << is_true[0][i] << '\n';
for (int k = 1; k <= 18; k++)
for (int i = 1; i <= N + M; i++) {
par[k][i] = par[k - 1][par[k - 1][i]];
mx[k][i] = max(mx[k - 1][i], mx[k - 1][par[k - 1][i]]);
is_true[k][i] = is_true[k - 1][i] | is_true[k - 1][par[k - 1][i]];
}
}
int getLCA(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
for (int k = 18; k >= 0; k--)
if (depth[par[k][x]] >= depth[y])
x = par[k][x];
if (x == y) return x;
for (int k = 18; k >= 0; k--) {
if (par[k][x] != par[k][y]) {
x = par[k][x];
y = par[k][y];
}
}
return par[0][y];
}
int getMinimumFuelCapacity(int x, int y) {
x++; y++;
if (find_set(x) != find_set(y)) return -1;
int lca = getLCA(x, y), ans = 0; bool valid = false;
//out << lca << '\n';
for (int k = 18; k >= 0; k--)
if (depth[par[k][x]] >= depth[lca]) {
ans = max(ans, mx[k][x]);
valid |= is_true[k][x];
x = par[k][x];
}
for (int k = 18; k >= 0; k--)
if (depth[par[k][y]] >= depth[lca]) {
ans = max(ans, mx[k][y]);
valid |= is_true[k][y];
x = par[k][y];
}
if (valid) return ans;
for (int k = 18; k >= 0; k--) {
if (!par[k][x]) continue;
if (!is_true[k][x]) {
ans = max(ans, mx[k][x]);
x = par[k][x];
}
//cout << "Jump " << k << ' ' << x << ' ';
}
//cout << '\n';
return max(ans, mx[0][x]);
//return -1;
}
/*
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M;
cin >> N >> M;
vector<int> U, V, W;
for (int i = 1; i <= M; i++) {
int u, v, w;
cin >> u >> v >> w;
U.push_back(u);
V.push_back(v);
W.push_back(w);
}
init(N, M, U, V, W);
int Q;
cin >> Q;
while (Q--) {
int x, y;
cin >> x >> y;
cout << getMinimumFuelCapacity(x, y) << '\n';
}
return 0;
}*/
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/
