#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
struct dsu{
vector<int> p, d;
vector<bool> f;
vector<vector<int>> A, out;
int n;
void init(int ns){
n = ns;
d.resize(n + 1);
p.resize(n + 1);
f.resize(n + 1);
A.resize(n + 1);
out.resize(n + 1);
for (int i = 1; i <= n; i++){
out[i].assign(n + 1, -1);
p[i] = i;
A[i] = {i};
}
}
int get(int v){
if (p[v] != v){
p[v] = get(p[v]);
}
return p[v];
}
void unite(int x, int y, int w){
int a = get(x), b = get(y);
if (a == b){
if (!f[a]){
f[a] = 1;
for (int i: A[a]){
for (int j: A[a]){
assert(out[i][j] == -1);
out[i][j] = w;
}
}
}
return;
}
if (A[a].size() > A[b].size()) swap(a, b);
if (f[a] || f[b] || d[x] >= 2 || d[y] >= 2){
for (int i: A[a]){
for (int j: A[b]){
assert(out[i][j] == -1);
assert(out[j][i] == -1);
out[i][j] = out[j][i] = w;
}
}
f[b] = 1;
}
else {
d[x]++; d[y]++;
}
for (int i: A[a]) A[b].pb(i);
p[a] = b;
}
};
dsu T;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
n = N; m = M;
vector<arr3> ed;
for (int i = 0; i < m; i++){
ed.pb({W[i], U[i] + 1, V[i] + 1});
}
sort(ed.begin(), ed.end());
T.init(n);
for (auto [f, x, y]: ed){
T.unite(x, y, f);
}
}
int getMinimumFuelCapacity(int x, int y){
x++; y++;
if (T.out[x][y] == -1 && m != (n - 1)){
while (true){
x++;
}
}
return T.out[x][y];
}
