#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define X first
#define Y second
#define pb push_back
#include <vector>
int n,m,dg[100005],u_i,v_i,w_i,x,y,type=-1,flag=-1;
int node,w;
vector<pair<int,int> > g[100005],subtask2;
vector<pair<int,pair<int,int> > > v;
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(m==n-1&&flag==-1)
{
for(int i=2;i<=n;i++)
{
node=i;
w=g[i][0].Y;
subtask2.pb({w,node});
}
sort(subtask2.begin(),subtask2.end());
}
}
int getMinimumFuelCapacity(int X, int Y)
{
x=X+1;
y=Y+1;
if(type==-1)
{
if(n==3&&dg[1]==2&&dg[2]==2&&dg[3]==2)return v[2].X;
return -1;
}
if(m==n-1&&flag==-1)
{
if(x==1||y==1)return -1;
if(n<=3)return -1;
if(x==subtask2[0].Y&&y==subtask2[1].Y||x==subtask2[1].Y&&y==subtask2[0].Y)
{
return subtask2[2].X;
}
return max(g[x][0].Y,g[y][0].Y);
}
}
