#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 69;
vector<tuple<int, int, int>> edges;
int n, m, p[N], sz[N], dg, deg[N];
int root(int v) {
if (p[v] == v)
return v;
return p[v] = root(p[v]);
}
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
n = _n;
m = _m;
for (int i = 0;i < m;i++) {
edges.push_back({w[i], u[i], v[i]});
deg[u[i]]++;
deg[v[i]]++;
}
}
int getMinimumFuelCapacity(int x, int y) {
int ans = -1;
int l = 1, r = 10;
auto check = [&](int mid) {
for (int i = 0;i < n;i++) {
p[i] = i;
sz[i] = 1;
deg[i] = 0;
}
for (int i = 0;i < m;i++) {
int a, b, c;
tie(c, a, b) = edges[i];
if (c > mid)
continue;
deg[a]++;
deg[b]++;
int t = root(a);
int tt = root(b);
if (t != tt) {
if (sz[t] < sz[tt])
swap(t, tt);
sz[t] += sz[tt];
p[tt] = t;
}
}
if (root(x) != root(y))
return false;
bool ok = 0, all = 1;
for (int i = 0;i < n;i++) {
if (root(i) == root(x)) {
ok |= (deg[i] > 2);
all &= (deg[i] == 2);
}
}
return ok || all;
};
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return ans;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
*/
