#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
const int TAILLEMAXI=200*1000+2,INFINI=1000*1000*1000+2;
int nbvilles,nbroutes;
int deb,fin;
vector<int> adja[TAILLEMAXI]; // num de la route
vector<tuple<int,int,int>> routes; // deb,fin,longueur
bool possible[TAILLEMAXI];
int dist[TAILLEMAXI];
bool surchemin[TAILLEMAXI];
bool deja[TAILLEMAXI];
int vraidist[TAILLEMAXI];
int autre(int numroute,int moi){
if (get<0>(routes[numroute])==moi){
return get<1>(routes[numroute]);
}
return get<0>(routes[numroute]);
}
void dij(){
for (int i=0;i<nbvilles;i++){
dist[i]=-1;
}
set<pair<int,int>> encours;
encours.clear();
encours.insert({0,deb});
while (!encours.empty()){
int lmaxi=(*(encours.begin())).first;
int endroit=(*(encours.begin())).second;
encours.erase(encours.begin());
if (dist[endroit]==-1){
dist[endroit]=lmaxi;
if (endroit==fin){
return ;
}
for (auto i:adja[endroit]){
if (possible[i]){
int a=autre(i,endroit);
if (dist[a]==-1){
encours.insert({max(lmaxi,get<2>(routes[i])),a});
}
}
}
}
}
}
void bfs(){
deque<int> ec={};
ec.push_back(deb);
int d=0;
while (!ec.empty()){
int taille=ec.size();
for (int i=0;i<taille;i++){
int a=ec.front();
ec.pop_front();
if (vraidist[a]==-1){
vraidist[a]=d;
for (auto j:adja[a]){
ec.push_back(autre(j,a));
}
}
}
d++;
}
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
nbvilles=N;
nbroutes=M;
for (int i=0;i<nbroutes;i++){
routes.push_back(make_tuple(U[i],V[i],W[i]));
adja[U[i]].push_back(i);
adja[V[i]].push_back(i);
}
}
int getMinimumFuelCapacity(int X, int Y) {
deb=X;
fin=Y;
for (int i=0;i<nbroutes;i++){
possible[i]=true;
}
for (int i=0;i<nbvilles;i++){
surchemin[i]=false;
deja[i]=false;
vraidist[i]=-1;
}
bfs();
dij();
int distmin=dist[fin];
int ec=fin;
/*for (int i=0;i<nbvilles;i++){
cout<<vraidist[i]<<" ";
}
cout<<endl;
return 0;*/
while (ec!=deb){
deja[ec]=true;
if (ec!=fin){
surchemin[ec]=true;
}
int plusproche=INFINI,pos=-1,iroute=-1;
//cout<<dist[autre(adja[ec][v],ec)]<<endl;
for (auto i:adja[ec]){
if (dist[autre(i,ec)]!=-1 and dist[autre(i,ec)]<=dist[ec] and deja[autre(i,ec)]==false){
//cout<<42<<endl;
if (vraidist[autre(i,ec)]<plusproche){
pos=autre(i,ec);
plusproche=vraidist[autre(i,ec)];
iroute=i;
}
}
}
possible[iroute]=false;
ec=pos;
}
dij();
int nouvdist=dist[fin];
int rep=INFINI;
if (nouvdist!=-1){
rep=nouvdist;
}
int cote=INFINI;
int undeb=INFINI,deuxdeb=INFINI,unfin=INFINI,deuxfin=INFINI;
for (int i=0;i<nbroutes;i++){
if (possible[i] and (surchemin[get<0>(routes[i])] or surchemin[get<1>(routes[i])])){
cote=min(cote,get<2>(routes[i]));
}
if (possible[i] and (get<0>(routes[i])==deb or get<1>(routes[i])==deb)){
int l=get<2>(routes[i]);
if (l<=undeb){
deuxdeb=undeb;
undeb=l;
}
else if (l<=deuxdeb){
deuxdeb=l;
}
}
if (possible[i] and (get<0>(routes[i])==fin or get<1>(routes[i])==fin)){
int l=get<2>(routes[i]);
if (l<=unfin){
deuxfin=unfin;
unfin=l;
}
else if (l<=deuxfin){
deuxfin=l;
}
}
}
if (cote!=INFINI){
rep=min(rep,max(distmin,cote));
}
if (undeb!=INFINI and deuxdeb!=INFINI){
rep=min(rep,max(distmin,deuxdeb));
}
if (unfin!=INFINI and deuxfin!=INFINI){
rep=min(rep,max(distmin,deuxfin));
}
if (rep==INFINI){
return -1;
}
return rep;
}
