#pragma GCC optimize("Ofast")
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3*2e5-2;
int deg[mxN], boss[mxN], lk[mxN], rk[mxN], ndw[mxN], can_pass[mxN], nxt;
int find(int i) {
return i == boss[i] ? i : boss[i] = find(boss[i]);
}
void unite(int i, int j, int w) {
bool tri = ++deg[i] >= 3 || ++deg[j] >= 3;
i = find(i), j = find(j);
if (i == j) {
if (can_pass[i]) return;
lk[nxt] = i;
can_pass[nxt] = 1;
ndw[nxt] = w;
boss[i] = nxt++;
return;
}
lk[nxt] = i;
rk[nxt] = j;
can_pass[nxt] = tri || can_pass[i] || can_pass[j];
ndw[nxt] = w;
boss[i] = boss[j] = nxt++;
}
int up[mxN][20], depth[mxN];
void dfs(int cur, int prv, int d) {
depth[cur] = d;
up[cur][0] = prv;
for (int lvl = 0; lvl < 19; ++lvl)
up[cur][lvl+1] = up[up[cur][lvl]][lvl];
if (lk[cur] != -1) dfs(lk[cur], cur, d+1);
if (rk[cur] != -1) dfs(rk[cur], cur, d+1);
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
iota(boss, boss+mxN, 0);
fill(lk, lk+mxN, -1);
fill(rk, rk+mxN, -1);
nxt = n;
vector<int> s(m);
iota(s.begin(), s.end(), 0);
sort(s.begin(), s.end(), [&](int i, int j) { return w[i] < w[j]; });
for (int i : s) unite(u[i], v[i], w[i]);
for (int i = 1; i < n; ++i)
assert(find(i) == find(0));
dfs(find(0), find(0), 0);
}
int getMinimumFuelCapacity(int i, int j) {
if (depth[i] > depth[j]) swap(i, j);
for (int lvl = 19; lvl >= 0; --lvl)
if (depth[up[j][lvl]] >= depth[i])
j = up[j][lvl];
for (int lvl = 19; lvl >= 0; --lvl)
if (up[i][lvl] != up[j][lvl])
i = up[i][lvl], j = up[j][lvl];
if (i != j) i = up[i][0], j = up[j][0];
assert(i == j);
for (int lvl = 19; lvl >= 0; --lvl)
if (!can_pass[up[i][lvl]])
i = up[i][lvl];
if (!can_pass[i]) i = up[i][0];
if (!can_pass[i]) return -1;
return ndw[i];
}
