#include "swap.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e5 + 69;
const int inf = 1e9 + 69;
vector<tuple<int, int, int>> edges;
int n, m, p[N], sz[N], deg[N], lan[N];
vector<pair<int, int>> par[N];
vector<int> who[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]});
sort(edges.begin(), edges.end());
for (int i = 0;i < n;i++) {
sz[i] = 1;
p[i] = i;
par[i].push_back({0, i});
who[i].push_back(i);
lan[i] = inf;
}
for (auto u : edges) {
int c, b, a;
tie(c, a, b) = u;
int x = root(a);
int y = root(b);
if (x != y) {
if (sz[x] < sz[y])
swap(x, y);
for (auto j : who[y]) {
par[j].push_back({c, x});
who[x].push_back(j);
}
p[y] = x;
sz[x] += sz[y];
}
}
for (int i = 0;i < n;i++) {
p[i] = i;
sz[i] = 1;
who[i].clear();
who[i].push_back(i);
par[i].push_back({inf, par[i].back().s});
}
//lanac i lanac->lanac
//nelanac i lanac->nelanac
for (auto u : edges) {
int a, b, c;
tie(c, a, b) = u;
int x = root(a);
int y = root(b);
if (x != y) {
if (lan[x] != inf && lan[y] == inf) {
for (auto j : who[y])
lan[j] = c;
who[y].clear();
}
else if (lan[y] != inf && lan[x] == inf) {
for (auto j : who[x])
lan[j] = c;
who[x].clear();
}
else if (lan[x] == inf && lan[y] == inf && (deg[a] == 2 || deg[b] == 2)) {
for (auto j : who[x])
lan[j] = c;
who[x].clear();
for (auto j : who[y])
lan[j] = c;
who[y].clear();
}
if (sz[x] < sz[y])
swap(x, y);
for (auto j : who[y])
who[x].push_back(j);
sz[x] += sz[y];
p[y] = x;
}
else {
if (lan[x] != inf)
continue;
for (auto j : who[x])
lan[j] = c;
who[x].clear();
}
deg[a] += 1;
deg[b] += 1;
}
/*
for (int i = 0;i < n;i++)
cout << lan[i] << ' ';*/
}
int getMinimumFuelCapacity(int x, int y) {
int l = 1, r = 1e9, same = -1;
auto check = [&](int mid) {
pair<int, int> s = make_pair(mid, inf);
auto u = upper_bound(par[x].begin(), par[x].end(), s);
auto u1 = upper_bound(par[y].begin(), par[y].end(), s);
int i = u - par[x].begin();
int j = u1 - par[y].begin();
if (i == 0 || j == 0)
return false;
--i, --j;
return par[x][i].s == par[y][j].s;
};
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
same = mid;
r = mid - 1;
}
else
l = mid + 1;
}
int ans = max(same, max(lan[x], lan[y]));
if (ans > 1e9)
ans = -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
5 4
0 1 3
1 4 4
1 2 1
2 3 2
1
1 3
*/
