#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<climits>
#include"swap.h"
#define ff first
#define ss second
using namespace std;
int n, m;
vector<pair<int, pair<int, int>>> edges;
vector<vector<int>> binlift;
vector<int> depths;
vector<int> swapp;
int getp(int x, vector<int>& dsu) {
if (dsu[x] == x)return x;
return dsu[x] = getp(dsu[x], dsu);
}
void merge(int a, int b, int x, vector<int>& dsu) {
a = getp(a, dsu);
b = getp(b, dsu);
dsu[a] = x;
dsu[b] = x;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (int i = 0; i < m; i++) {
edges.push_back({ W[i], {U[i], V[i]} });
}
sort(edges.begin(), edges.end());
vector<int> dsu(n + m);
for (int i = 0; i < n + m; i++)dsu[i] = i;
swapp.assign(n + m, INT_MAX);
vector<vector<int>>child(n + m);
vector<int>deg(n, 0);
binlift.assign(n + m, vector<int>(20, -1));
for (int i = 0; i < m; i++) {
int a = edges[i].ss.ff;
int b = edges[i].ss.ss;
int oa = a;
int ob = b;
a = getp(a, dsu);
b = getp(b, dsu);
if (a != b) {
merge(a, b, i + n, dsu);
binlift[a][0] = i + n;
binlift[b][0] = i + n;
if (swapp[a] != INT_MAX || swapp[b] != INT_MAX || (deg[oa] >= 2 || deg[ob] >= 2)) {
swapp[i + n] = edges[i].ff;
}
child[i + n].push_back(a);
child[i + n].push_back(b);
}
else {
swapp[a] = min(swapp[a], edges[i].ff);
}
deg[oa]++;
deg[ob]++;
}
depths.assign(n + m, 0);
for (int i = n + m - 1; i >= 0; i--) {
for (int j = 0; j < child[i].size(); j++) {
depths[child[i][j]] = depths[i] + 1;
swapp[child[i][j]] = min(swapp[child[i][j]], swapp[i]);
}
}
for (int i = n + m - 1; i >= 0; i--) {
int j = 0;
while (binlift[i][j] != -1) {
binlift[i][j + 1] = binlift[binlift[i][j]][j];
j++;
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
if (depths[X] < depths[Y]) {
int tmp = X;
X = Y;
Y = tmp;
}
while (depths[X] != depths[Y]) {
X = binlift[X][floor(log2(depths[X] - depths[Y]))];
}
while (X != Y) {
int i = 19;
while (binlift[X][i] == binlift[Y][i] && i > 0)i--;
X = binlift[X][i];
Y = binlift[Y][i];
}
return swapp[X] == INT_MAX ? -1 : swapp[X];
}
/*signed main() {
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 a, b;
cin >> a >> b;
cout << getMinimumFuelCapacity(a, b) << "\n";
}
}*/
