#include "swap.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
int NN;
int MM;
int all[200005];
bool use[200005];
bool use2[200005];
bool have2[200005];
bool have3[200005];
int Father[200005];
int y;
int ans=0;
int how=0;
vector < pair < pair < int , int > , int > > Next[200005];
vector < pair < pair < int , int > , int > > Next2[200005];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > dd;
struct A
{
int u,v,w;
int con;
}edge[200005];
vector < int > have;
bool cmp(pair < pair < int , int > , int > a,pair < pair < int , int > , int > b)
{
return a.first.second<b.first.second;
}
bool cmp2(A a,A b)
{
return a.w<b.w;
}
bool F(int here,int fa)
{
if(here==y)
{
//printf("%d\n",here);
have.push_back(here);
have2[here]=1;
return 1;
}
for(auto i:Next2[here])
{
if(i.first.first==fa) continue;
if(F(i.first.first,here))
{
//printf("%d\n",here);
ans=max(ans,i.first.second);
use[i.second]=1;
have.push_back(here);
have2[here]=1;
return 1;
}
}
return 0;
}
int Find(int here)
{
if(Father[here]==here) return here;
Father[here]=Find(Father[here]);
return Father[here];
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W)
{
NN=N;
MM=M;
int i;
for(i=0;i<M;i++)
{
Next[U[i]].push_back(make_pair(make_pair(V[i],W[i]),i));
Next[V[i]].push_back(make_pair(make_pair(U[i],W[i]),i));
edge[i].u=U[i];
edge[i].v=V[i];
edge[i].w=W[i];
edge[i].con=i;
}
for(i=0;i<N;i++)
{
Father[i]=i;
sort(Next[i].begin(),Next[i].end(),cmp);
}
sort(edge,edge+M,cmp2);
for(i=0;i<M;i++)
{
if(Find(edge[i].u)==Find(edge[i].v)) continue;
Father[Find(edge[i].u)]=Find(edge[i].v);
Next2[edge[i].u].push_back(make_pair(make_pair(edge[i].v,edge[i].w),edge[i].con));
Next2[edge[i].v].push_back(make_pair(make_pair(edge[i].u,edge[i].w),edge[i].con));
}
}
int getMinimumFuelCapacity(int x, int y)
{
int t=2e9,t2=-1,con=0,i,j,a,b;
::y=y;
for(i=0;i<MM;i++) use[i]=0;
for(i=0;i<=NN;i++) have2[i]=0;
ans=0;
have.clear();
F(x,-1);
for(auto i:have)
{
con=0;
t2=-1;
for(auto j:Next[i])
{
if(use[j.second]) continue;
if(i==x||i==y) continue;
con++;
if((i!=x&&i!=y&&con>=1)||con>=2)
{
//printf("%d %d\n",i,j.first.second);
t2=j.first.second;
break;
}
}
if(t2!=-1) t=min(t,t2);
}
for(auto i:Next[x])
{
if(use[i.second]) continue;
for(j=0;j<=NN;j++) use2[j]=0;
for(j=0;j<=MM;j++) have3[j]=0;
have3[i.second]=1;
dd.push(make_pair(i.first.second,i.first.first));
while(!dd.empty())
{
a=dd.top().first;
b=dd.top().second;
dd.pop();
if(use2[b])
{
t=min(t,a);
break;
}
if(have2[b])
{
t=min(t,a);
break;
}
use2[b]=1;
con=0;
for(auto j:Next[b])
{
if(have3[j.second]||use[j.second]) continue;
con++;
if(con==2) t=min(t,max(j.first.second,a));
have3[j.second]=1;
dd.push(make_pair(max(j.first.second,a),j.first.first));
}
}
while(!dd.empty()) dd.pop();
}
for(auto i:Next[y])
{
if(use[i.second]) continue;
for(j=0;j<=NN;j++) use2[j]=0;
for(j=0;j<=MM;j++) have3[j]=0;
have3[i.second]=1;
dd.push(make_pair(i.first.second,i.first.first));
while(!dd.empty())
{
a=dd.top().first;
b=dd.top().second;
dd.pop();
if(use2[b])
{
t=min(t,a);
break;
}
if(have2[b])
{
t=min(t,a);
break;
}
use2[b]=1;
con=0;
for(auto j:Next[b])
{
if(have3[j.second]||use[j.second]) continue;
have3[j.second]=1;
con++;
if(con==2) t=min(t,max(j.first.second,a));
dd.push(make_pair(max(j.first.second,a),j.first.first));
}
}
while(!dd.empty()) dd.pop();
}
if(t>=2000000000) return -1;
return max(t,ans);
}
