#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];
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 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;
}
dij();
int distmin=dist[fin];
int ec=fin;
while (ec!=deb){
if (ec!=fin){
surchemin[ec]=true;
}
int v=0;
while (dist[autre(adja[ec][v],ec)]==-1 or dist[autre(adja[ec][v],ec)]>dist[ec]){
v++;
}
possible[adja[ec][v]]=false;
ec=autre(adja[ec][v],ec);
}
dij();
int nouvdist=dist[fin];
int rep=INFINI;
if (nouvdist!=-1){
rep=nouvdist;
}
int cote=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 (cote!=INFINI){
rep=min(rep,max(distmin,cote));
}
if (rep==INFINI){
return -1;
}
return rep;
}
