#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#include "swap.h"
typedef vector<int> vi;
const int N = 3e5, L = 19, INF = int(1e9) + 1;
int p[N];
int find(int i) { return p[i] == i ? i : p[i] = find(p[i]); }
int tag1[N], tag2[N], ans[N];
vi g[N];
int pp[L][N], dd[N];
void dfs(int p, int i) {
pp[0][i] = p;
for (int l = 1; l < L; l++) pp[l][i] = pp[l - 1][pp[l - 1][i]];
ans[i] = min(ans[i], max(tag1[i], tag2[i]));
for (int j : g[i]) {
dd[j] = dd[i] + 1;
ans[j] = min(ans[j], ans[i]);
dfs(i, j);
}
}
int lca(int i, int j) {
if (dd[i] < dd[j]) swap(i, j);
int k = dd[i] - dd[j];
for (int l = 0; l < L; l++)
if (k >> l & 1) i = pp[l][i];
if (i == j) return i;
for (int l = L - 1; l >= 0; l--)
if (pp[l][i] != pp[l][j]) i = pp[l][i], j = pp[l][j];
return pp[0][i];
}
void init(int n, int m, vi u, vi v, vi w) {
vi order(m);
for (int i = 0; i < m; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j) { return w[i] < w[j]; });
vi d(n);
for (int i = 0; i < n + m; i++) {
p[i] = i;
ans[i] = tag1[i] = tag2[i] = INF;
}
int root = -1;
for (int h : order) {
int i = u[h], j = v[h];
d[i]++;
d[j]++;
bool swap = d[i] >= 3 || d[j] >= 3;
if (find(i) != find(j)) {
g[n + h].push_back(find(i));
g[n + h].push_back(find(j));
tag1[n + h] = min(tag1[n + h], w[h]);
tag2[n + h] = min(tag2[find(i)], tag2[find(j)]);
if (swap) tag2[n + h] = min(tag2[n + h], w[h]);
p[find(i)] = p[find(j)] = n + h;
root = n + h;
} else {
int c = find(i);
tag2[c] = min(tag2[c], w[h]);
}
}
dfs(root, root);
}
int getMinimumFuelCapacity(int i, int j) {
int p = lca(i, j);
return ans[p] == INF ? -1 : ans[p];
}
