#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int lg = 20;
int n, m, gr[maxn], ds[maxn], dsz[maxn], mn[maxn];
vector<int> mn0[maxn];
vector<pair<int,pair<int,int>>> edgs;
vector<pair<int,int>> g[maxn];
int find(int u) {
if(ds[u] == u) return u;
return ds[u] = find(ds[u]);
}
void join(int u, int v, int id) {
gr[u]++;
gr[v]++;
int mxgr = max(gr[u],gr[v]);
u = find(u);
v = find(v);
if(u == v || mxgr >= 3 || mn[u] != -1 || mn[v] != -1) {
if(mn0[u].size()) {
for(auto x : mn0[u]) {
mn[x] = id;
}
mn0[u].clear();
}
if(mn0[v].size()) {
for(auto x : mn0[v]) {
mn[x] = id;
}
mn0[v].clear();
}
}
if(u == v) return;
if(dsz[u] < dsz[v]) swap(u,v);
for(auto x : mn0[v]) {
mn0[u].pb(x);
}
dsz[u]+= dsz[v];
ds[v] = u;
}
void init(int N, int M, vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
for(auto i = 0; i < m; i++) {
edgs.pb(mp(W[i],mp(U[i],V[i])));
}
sort(all(edgs));
for(int i = 0; i < n; i++) {
gr[i] = 0;
mn[i] = -1;
ds[i] = i;
dsz[i] = 1;
mn0[i].clear();
mn0[i].pb(i);
}
for(int i = 0; i < m; i++) {
int u = edgs[i].sc.fr;
int v = edgs[i].sc.sc;
// if(find(u) != find(v)) {
// g[u].pb(mp(v,i));
// g[v].pb(mp(u,i));
// }
join(u,v,i);
}
// dfs(0,0,-1);
}
int getMinimumFuelCapacity(int x, int y) {
for(int i = 0; i < n; i++) {
gr[i] = 0;
mn[i] = -1;
ds[i] = i;
dsz[i] = 1;
mn0[i].clear();
mn0[i].pb(i);
}
for(int i = 0; i < m; i++) {
int u = edgs[i].sc.fr;
int v = edgs[i].sc.sc;
join(u,v,i);
if(find(u) == find(v) && mn[u] != -1 && mn[v] != -1) return edgs[i].fr;
}
return -1;
}
