#include <bits/stdc++.h>
using namespace std;
const int N = 300000, K = 19;
vector<int> adj[N];
int par[N], comp[N], deg[N], cycle[N], deg3[N];
int T[K][N], wei[K][N], dep[N];
int nxt = 0;
int find(int u) {
return par[comp[u]] == comp[u]
? comp[u]
: comp[u] = find(comp[u]);
}
void merge(int u, int v, int w) {
int d = max(++deg[u], ++deg[v]);
u = find(u), v = find(v);
par[u] = par[v] = comp[u] = comp[v] = nxt;
cycle[nxt] = u == v | cycle[u] | cycle[v];
deg3[nxt] = d == 3 | deg3[u] | deg3[v];
par[nxt] = comp[nxt] = nxt;
adj[nxt].push_back(u);
if (u != v)
adj[nxt].push_back(v);
wei[0][u] = wei[0][v] = w;
nxt++;
}
void dfs(int u, int p = -1) {
for (int v : adj[u]) {
if (v == p) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
vector<int> edges(m);
for (int i = 0; i < m; i++) edges[i] = i;
sort(edges.begin(), edges.end(), [&](int i, int j) { return W[i] < W[j]; });
for (int i = 0; i < n; i++) {
par[i] = comp[i] = i;
nxt++;
}
for (int i : edges) {
merge(U[i], V[i], W[i]);
}
for (int u = 0; u < n+m; u++)
T[0][u] = par[u];
for (int i = 0; i < K-1; i++) {
for (int u = 0; u < n+m; u++) {
T[i+1][u] = T[i][T[i][u]];
wei[i+1][u] = max(wei[i][u], wei[i][ T[i][u] ]);
}
}
dfs(find(0));
}
int getMinimumFuelCapacity(int x, int y) {
int ans = 0;
if (dep[x] > dep[y]) swap(x, y);
int d = dep[y] - dep[x];
for (int i = 0; i < K; i++) if ((d >> i) & 1) {
ans = max(ans, wei[i][y]);
y = T[i][y];
}
if (x != y) {
for (int i = K-1; i >= 0; i--) {
if (T[i][x] != T[i][y]) {
ans = max(ans, max(wei[i][x], wei[i][y]));
x = T[i][x];
y = T[i][y];
}
}
ans = max(ans, max(wei[0][x], wei[0][y]));
x = T[0][x];
y = T[0][y];
}
if (cycle[x] | deg3[x]) return ans;
for (int i = K-1; i >= 0; i--) {
if (!cycle[T[i][x]] && !deg3[T[i][x]]) {
ans = max(ans, wei[i][x]);
x = T[i][x];
}
}
ans = max(ans, wei[0][x]);
x = T[0][x];
if (cycle[x] | deg3[x]) return ans;
return -1;
}
//int main() {
// init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
// cout << getMinimumFuelCapacity(1, 2) << '\n';
// cout << getMinimumFuelCapacity(2, 4) << "\n";
// cout << getMinimumFuelCapacity(0, 1) << "\n";
// const int n = 100000;
// vector<int> U(n-1), V(n-1), W(n-1);
// for (int i = 0; i < n-1; i++) {
// U[i] = 0;
// V[i] = i+1;
// W[i] = i+1;
// }
// using namespace chrono;
// auto start = high_resolution_clock ::now();
// init(n, n-1, U, V, W);
// auto stop = high_resolution_clock ::now();
// cout << duration_cast<milliseconds>(stop-start).count();
//}
