#include <bits/stdc++.h>
#include "swap.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 2e9;
struct Dsu {
int link[N];
void Init(int n) {
for (int i = 1; i <= n; i++) link[i] = i;
}
int Find(int x) {
if (x == link[x]) return x;
return link[x] = Find(link[x]);
}
void Unite(int u, int v) {
u = Find(u); v = Find(v);
if (u == v) return;
link[v] = u;
}
}dsu;
vector<array<int, 3>> g[N];
int par[N][17], mxe[N][17], gmn[N][17], in[N], out[N], dep[N], mnb[N], parval[N], gmnval[N], tsz;
void Dfs(int s, int e) {
in[s] = ++tsz;
par[s][0] = e;
mxe[s][0] = parval[s];
gmn[s][0] = inf;
if (g[s].size() >= 3) gmn[s][0] = g[s][2][0];
gmnval[s] = gmn[s][0];
for (int i = 1; i < 17; i++) {
par[s][i] = par[par[s][i - 1]][i - 1];
mxe[s][i] = max(mxe[s][i - 1], mxe[par[s][i - 1]][i - 1]);
gmn[s][i] = min(gmn[s][i - 1], gmn[par[s][i - 1]][i - 1]);
}
mnb[s] = inf;
for (auto u : g[s]) {
if (u[1] != e && u[2] == 1) {
parval[u[1]] = u[0];
dep[u[1]] = dep[s] + 1;
Dfs(u[1], s);
smin(mnb[s], mnb[u[1]]);
}
if (u[2] == 0) {
smin(mnb[s], u[0]);
}
}
out[s] = tsz;
}
bool Ancestor(int u, int v) {
return in[u] <= in[v] && out[v] <= out[u];
}
int Lca(int u, int v) {
if (Ancestor(u, v)) return u;
if (Ancestor(v, u)) return v;
for (int i = 16; i >= 0; i--) {
if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i];
}
return par[u][0];
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
vector<array<int, 3>> e(m);
for (int i = 0; i < m; i++) {
u[i] += 1;
v[i] += 1;
e.push_back({w[i], u[i], v[i]});
}
dsu.Init(n);
sort(e.begin(), e.end());
for (auto u : e) {
if (dsu.Find(u[1]) == dsu.Find(u[2])) {
g[u[1]].push_back({u[0], u[2], 0});
g[u[2]].push_back({u[0], u[1], 0});
}
else {
dsu.Unite(u[1], u[2]);
g[u[1]].push_back({u[0], u[2], 1});
g[u[2]].push_back({u[0], u[1], 1});
}
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end());
}
for (int i = 0; i < 17; i++) gmn[0][i] = inf;
Dfs(1, 0);
}
int GetMxFromPath(int u, int v) {
int ans = 0;
int raz = dep[u] - dep[v];
for (int i = 16; i >= 0; i--) {
if ((1 << i) & raz) {
smax(ans, mxe[u][i]);
u = par[u][i];
}
}
return ans;
}
int GetMnFromPath(int u, int v) {
int ans = inf;
int raz = dep[u] - dep[v];
for (int i = 16; i >= 0; i--) {
if ((1 << i) & raz) {
smin(ans, gmn[u][i]);
u = par[u][i];
}
}
return ans;
}
int Kth(int u, int k) {
for (int i = 16; i >= 0; i--) {
if ((1 << i) & k) u = par[u][i];
}
return u;
}
int getMinimumFuelCapacity(int x, int y) {
x += 1; y += 1;
int lca = Lca(x, y);
int o = max(GetMxFromPath(x, lca), GetMxFromPath(y, lca));
smax(o, parval[lca]);
int xx = par[x][0];
if (x == lca) xx = Kth(y, dep[y] - dep[x] - 1);
int yy = par[y][0];
if (y == lca) yy = Kth(x, dep[x] - dep[y] - 1);
int ans = inf;
if (xx != y && yy != x) {
int oo = min(GetMnFromPath(xx, lca), GetMnFromPath(yy, lca));
smin(oo, gmnval[lca]);
smin(ans, max(o, oo));
}
smin(ans, max(o, max(mnb[x], mnb[y])));
if (ans == inf) ans = -1;
return ans;
}
