#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
// global
int n,m;
int deg[100005],l[300005],mn[300005],deep[300005];
int spa[300005][20];
vector<int> v[300005];
priority_queue<pair<int,pair<int,int> > > pq;
int fi(int idx)
{
if(l[idx] == idx) return idx;
return l[idx] = fi(l[idx]);
}
void uni(int x,int y,int w)
{
bool chk = deg[x] > 1 | deg[y] > 1;
deg[x]++;
deg[y]++;
x = fi(x), y = fi(y);
if(x == y)
{
if(!mn[x])
mn[x] = w;
return ;
}
l[x] = l[y] = n;
if(chk || mn[x] || mn[y])
mn[n] = w;
v[n].pb(x);
v[n].pb(y);
n++;
}
void dfs(int nw,int fa)
{
for(auto go: v[nw])
{
if(go == fa) continue;
if(!mn[go]) mn[go] = mn[nw];
deep[go] = deep[nw] + 1;
spa[go][0] = nw;
dfs(go, nw);
}
}
int query(int a,int b)
{
if(deep[a] > deep[b]) swap(a,b);
int dif = deep[b] - deep[a];
for(int i = 0; i < 20; i++)
if((1<<i)&dif)
b = spa[b][i];
if(a == b) return mn[a];
for(int i = 19; i >= 0; i--)
{
if(spa[a][i] != spa[b][i])
{
a = spa[a][i];
b = spa[b][i];
}
}
return mn[spa[a][0]];
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W)
{
n = N, m = M;
memset(spa, -1, sizeof(spa));
for(int i = 0; i < 300005; i++)
l[i] = i;
for(int i = 0; i < m; i++)
pq.push({-W[i],{U[i],V[i]}});
while(!pq.empty())
{
int x = pq.top().s.f, y = pq.top().s.s, w = -pq.top().f;
pq.pop();
uni(x,y,w);
}
dfs(n - 1, -1);
for(int i = 0; i < 300005; i++)
if(!mn[i]) mn[i] = -1;
for(int j = 1; j < 20; j++)
{
for(int i = 0; i < n; i++)
{
if(spa[i][j - 1] == -1) continue;
spa[i][j] = spa[spa[i][j - 1]][j - 1];
}
}
return ;
}
int getMinimumFuelCapacity(int X, int Y)
{
return query(X,Y);
}
