//InTheNameOfGOD
//PRS;)
#include<bits/stdc++.h>
#include "swap.h"
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define pb push_back
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pi;
constexpr ll inf = 2e9, xm = 2e5 + 5, xn = 1e5 + 5;
vector<pl> p[xn];
vector<ll> g[xn];
pi e[xm];
ll ans[xn], d[xn], n, m;
void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W)
{
n = N, m = M;
rep(i, 0, N) p[i].pb({0, i}), g[i].pb(i), ans[i] = inf;
rep(i, 0, M) e[i] = {W[i], {U[i], V[i]}};
sort(e, e + M);
rep(i, 0, M)
{
ll v = e[i].X, x = e[i].Y.X, y = e[i].Y.Y;
ll x1 = p[x].back().Y, y1 = p[y].back().Y;
if(x1 == y1)
{
ans[x1] = min(ans[x1], v);
continue;
}
if(g[x1].size() < g[y1].size()) swap(x1, y1), swap(x, y);
ans[x1] = min(ans[x1], max(ans[y1], v)), d[x]++, d[y]++;
if(d[x] > 2 || d[y] > 2) ans[x1] = min(ans[x1], v);
for(ll u : g[y1]) p[u].pb({v, x1}), g[x1].pb(u);
}
}
ll getMinimumFuelCapacity(ll x, ll y)
{
ll i = p[x].size(), j = p[y].size(), ret = inf;
i--, j--;
while(i >= 0 && j >= 0 &&p[x][i].Y == p[y][j].Y)
ret = min(ret, max(ans[p[x][i].Y], max(p[x][i].X, p[y][j].X))), i--, j--;
return (ret >= inf ? -1 : ret);
}
