#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define SZ(a) (int)a.size()
using ll = long long;
const int maxn = (int)1e5+10;
const int INF = (ll)1e9;
vector<pair<int,int>> adj[maxn];
ll dis[maxn]; int tot = 0;
int par[maxn];
bool vis[maxn];
int n, m, p[maxn], sz[maxn];
int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }
bool unionSet(int i, int j){
int x = findSet(i), y = findSet(j);
if(x==y) return false;
if(sz[x] < sz[y]) swap(x,y);
p[y]=x, sz[x]+=sz[y];
return true;
}
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++){
adj[u[i]].pb({v[i],w[i]});
adj[v[i]].pb({u[i],w[i]});
}
}
bool chk(int w, int x, int y){
int mx_deg = 0, cnt = 0;
for(int i = 0; i < n; i++) p[i] = i, sz[i] = 1;
for(int i = 0; i < n; i++)
for(auto u : adj[i])
if(u.se<=w) unionSet(i,u.fi);
if(!isSameSet(x,y)) return 0;
bool ok = true;
for(int i = 0; i < n; i++){
if(!isSameSet(i,x)) continue;
int deg = 0;
for(auto u : adj[i])
if(u.se<=w) deg++;
if(mx_deg<deg) mx_deg=deg,cnt=1;
else if(mx_deg==deg) cnt++;
if(deg==1) ok=0;
}
if(mx_deg>=3) return 1;
if(mx_deg<=1) return 0;
return ok;
}
/*
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
*/
int getMinimumFuelCapacity(int x, int y) {
int l = 1, r = INF+1;
while(l<r){
int mid = (l+r)/2;
if(chk(mid,x,y)) r=mid;
else l=mid+1;
}
return (l==INF+1?-1:l);
}
