#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;
int p[maxn][lg+2], w[maxn][lg+2], h[maxn];
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;
}
int ds1[maxn], dsz1[maxn];
int find1(int u) {
if(ds1[u] == u) return u;
return ds1[u] = find1(ds1[u]);
}
void join1(int u, int v) {
u = find1(u);
v = find1(v);
if(u == v) return;
if(dsz1[u] < dsz1[v]) swap(u,v);
dsz1[u]+= dsz1[v];
ds1[v] = u;
}
void dfs(int u, int ant, int antw) {
p[u][0] = ant;
w[u][0] = antw;
for(int i = 1; i <= lg; i++) {
p[u][i] = p[p[u][i-1]][i-1];
w[u][i] = max(w[u][i-1],w[p[u][i-1]][i-1]);
}
for(auto V : g[u]) if(V.fr != ant) {
h[V.fr] = h[u]+1;
dfs(V.fr,u,V.sc);
}
}
int lca(int u, int v) {
int ans = 0;
if(h[u] < h[v]) swap(u,v);
for(int i = lg; i >= 0; i--) {
if(h[p[u][i]] >= h[v]) {
ans = max(ans, w[u][i]);
u = p[u][i];
}
}
if(u == v) return ans;
for(int i = lg; i >= 0; i--) {
if(p[u][i] != p[v][i]) {
ans = max(ans,w[u][i]);
u = p[u][i];
ans = max(ans,w[v][i]);
v = p[v][i];
}
}
ans = max(ans, w[u][0]);
ans = max(ans, w[v][0]);
return ans;
}
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);
p[i][0] = -1;
}
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) {
if(mn[x] == -1 || mn[y] == -1) return -1;
return edgs[max({lca(x,y),mn[x],mn[y]})].fr;
}
