#include "swap.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int inf = 1001001001;
class unionfind {
int n;
vi par, rank;
public:
unionfind(int n) : n(n), par(n, -1), rank(n, 0) {}
int root(int x) {
if (par[x] < 0) return x;
return par[x] = root(par[x]);
}
bool same(int x, int y) {
return root(x) == root(y);
}
bool merge(int x, int y) {
x = root(x), y = root(y);
if (x == y) return false;
if (rank[x] < rank[y]) swap(x, y);
if (rank[x] == rank[y]) rank[x]++;
par[x] += par[y];
par[y] = x;
return true;
}
};
namespace {
int n;
int m;
vvp G;
vi deg;
int mx_w;
int mx_deg;
bool cycle;
}
void init(int _n, int _m, vi u, vi v, vi w) {
n = _n;
m = _m;
G.resize(n);
deg.resize(n);
mx_w = 0;
rep(i, m) {
G[u[i]].eb(v[i], w[i]);
G[v[i]].eb(u[i], w[i]);
deg[u[i]]++;
deg[v[i]]++;
chmax(mx_w, w[i]);
}
cycle = all_of(all(deg), [](int i) { return i == 2; });
mx_deg = *max_element(all(deg));
sort(all(G[0]), [](P a, P b) { return a.second < b.second; });
}
// subtask 2
int getMinimumFuelCapacity(int x, int y) {
// subtask 1
if (mx_deg <= 2) {
return (cycle ? mx_w : -1);
}
// subtask 2
if (m <= n - 1 and deg[0] == m) {
if (n <= 3) return -1;
if (x == 0) {
int ans = G[y][0].second;
int cnt = 0;
for (auto[v, w] : G[0]) {
if (v == y) continue;
chmax(ans, w);
cnt++;
if (cnt == 2) break;
}
return ans;
} else {
int ans = max(G[x][0].second, G[y][0].second);
for (auto[v, w] : G[0]) {
if (v == x or v == y) continue;
chmax(ans, w);
break;
}
return ans;
}
}
// subtask 3,4
{
int ok = inf, ng = 0;
auto f = [&](int l) -> bool {
unionfind uf(n);
vi d(n);
rep(i, n) for (auto[j, w] : G[i]) {
if (i > j) continue;
if (w > l) continue;
uf.merge(i, j);
d[i]++;
d[j]++;
}
if (!uf.same(x, y)) return false;
bool res = true;
rep(i, n) {
if (!uf.same(i, x)) continue;
if (d[i] > 2) return true;
if (d[i] == 1) res = false;
}
return res;
};
if (!f(ok)) return -1;
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
}
