#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define X first
#define Y second
#define pb push_back
int n,m,dg[100005],u_i,v_i,w_i,x,y,type=-1,flag=-1;
int deter=2,d[1005][1005],st,md,ed,u1,u2,w,node;
vector<pair<int,int> > g[100005];
vector<pair<int,pair<int,int> > > v;
queue<pair<int,int> > q;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n=N;
m=M;
for(int i=0;i<m;i++)
{
u_i=U[i]+1;
v_i=V[i]+1;
w_i=W[i];
g[u_i].pb({v_i,w_i});
g[v_i].pb({u_i,w_i});
++dg[u_i];
++dg[v_i];
v.push_back({w_i,{u_i,v_i}});
if(u_i!=1)flag=0;
}
sort(v.begin(),v.end());
for(int i=1;i<=n;i++)
{
if(dg[i]>2)
{
type=0;
}
}
if(type==-1)
{
deter=0;
for(int i=1;i<=n;i++)if(dg[i]!=2)deter=-1;
}
}
int getMinimumFuelCapacity(int X, int Y)
{
x=X+1;
y=Y+1;
if(type==-1)
{
if(deter==0)return v[v.size()-1].X;
return -1;
}
if(m==n-1&&flag==-1)
{
if(m<=2)return -1;
if(x==1)
{
if(g[y][0].Y>v[2].X)return g[y][0].Y;
return v[2].X;
}
if(x==v[0].Y.Y&&y==v[1].Y.Y||x==v[1].Y.Y&&y==v[0].Y.Y)return v[2].X;
return max(g[x][0].Y,g[y][0].Y);
}
if(n<=1000&&m<=2000)
{
st=0;
ed=v.size()-1;
while(ed>=st)
{
md=(st+ed)/2;
memset(d,0,sizeof d);
d[x][y]=1;
q.push({x,y});
while(!q.empty())
{
u1=q.front().X;
u2=q.front().Y;
q.pop();
for(int i=0;i<g[u1].size();i++)
{
node=g[u1][i].X;
w=g[u1][i].Y;
if(v[md].X>=w&&node!=u2&&d[node][u2]==0)
{
d[node][u2]=1;
q.push({node,u2});
}
}
for(int i=0;i<g[u2].size();i++)
{
node=g[u2][i].X;
w=g[u2][i].Y;
if(v[md].X>=w&&node!=u1&&d[u1][node]==0)
{
d[u1][node]=1;
q.push({u1,node});
}
}
}
if(d[y][x]==1)
{
ed=md-1;
}else
{
st=md+1;
}
}
return v[st].X;
}
}
