#include "swap.h"
#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=3e5+50;
const int LOG=18;
int n, m, uk;
vector <pip> v;
vector <int> ls[N];
int P[N], lanac[N], deg[N], dep[N];
int cnt[N][4], par[LOG+1][N];
int name(int x) {
if (x==P[x]) return x;
P[x]=name(P[x]);
return P[x];
}
void check(int x, int val) {
if (lanac[x]!=INF) return;
if (cnt[x][3]) lanac[x]=val;
else if (!cnt[x][1] && cnt[x][2]) lanac[x]=val;
#if DEBUG
if (lanac[x]!=INF) printf("%d ima lanac %d\n", x, val);
#endif // DEBUG
}
void pov_deg(int x, int val) {
if (deg[x]>=3) return;
int y=name(x);
cnt[y][deg[x]]--; deg[x]++; cnt[y][deg[x]]++;
check(y, val);
}
void dfs(int node, int papi) {
dep[node]=dep[papi]+1;
par[0][node]=papi;
lanac[node]=min(lanac[node], lanac[papi]);
for (int sus:ls[node]) dfs(sus, node);
}
void build() {
for (int i=1; i<=LOG; ++i) {
for (int j=0; j<uk; ++j) {
par[i][j]=par[i-1][par[i-1][j]];
}
}
}
int lca(int x, int y) {
if (dep[x]<dep[y]) swap(x, y);
for (int i=LOG; i>=0; --i) {
if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
}
if (x==y) return x;
for (int i=LOG; i>=0; --i) {
if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
}
return par[0][x];
}
void init(int NN, int MM, vector<int> U, vector<int> V, vector<int> W) {
n=NN, m=MM;
for (int i=0; i<m; ++i) v.pb(mp(W[i], mp(U[i], V[i])));
sort(v.begin(), v.end());
for (int i=0; i<2*n; ++i) P[i]=i;
for (int i=0; i<n; ++i) cnt[i][0]=1;
memset(lanac, INF, sizeof lanac);
uk=n;
for (pip pp:v) {
#if DEBUG
printf("edge: (%d <-> %d) %d\n", pp.Y.X, pp.Y.Y, pp.X);
#endif
int x=name(pp.Y.X), y=name(pp.Y.Y);
int curr=x;
if (x!=y) {
curr=uk++;
P[y]=P[x]=curr;
#if DEBUG
printf("parent od %d i %d je %d\n", x, y, curr);
#endif // DEBUG
ls[curr].pb(x); ls[curr].pb(y);
for (int i=0; i<4; ++i) cnt[curr][i]=cnt[x][i]+cnt[y][i];
lanac[curr]=min(lanac[x], lanac[y]);
lanac[curr]=max(lanac[curr], pp.X);
}
pov_deg(pp.Y.X, pp.X); pov_deg(pp.Y.Y, pp.X);
#if DEBUG
printf("\n");
#endif // DEBUG
}
#if DEBUG
for (int i=0; i<uk; ++i) printf("node: %d, lanac: %d\n", i, lanac[i]);
#endif
dfs(name(0), name(0));
build();
}
int getMinimumFuelCapacity(int x, int y) {
int lc=lca(x, y);
return lanac[lc]==INF ? -1 : lanac[lc];
}
