#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
int n;
// weight then node
vector<vector<pair<int, int>>> adj;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N;
adj = vector<vector<pair<int, int>>>(N);
for(int i=0; i<M; i++) {
adj[U[i]].push_back({W[i], V[i]});
adj[V[i]].push_back({W[i], U[i]});
}
for(int i=0; i<N; i++) sort(adj[i].begin(), adj[i].end());
}
int ans=0;
set<pair<int, int>> noUse;
vector<int> dijkstra(int s, int e) {
vector<int> par(n), dis(n, 1e9); dis[s]=0;
vector<bool> vis(n, false);
priority_queue<pair<int, int>> q; q.push({0, s});
while(!q.empty()) {
int node = q.top().second; q.pop();
if(vis[node]) continue;
vis[node]=true;
if(node == e) {
ans=dis[e]; break;
}
for(auto [w, child] : adj[node]) if(!noUse.count({node, child})) {
if(dis[child] > max(dis[node], w)) {
dis[child]=max(dis[node], w);
par[child]=node;
q.push({-dis[child], child});
}
}
}
vector<int> path; path.push_back(e);
for(int i=e; i!=s; i=par[i]) {
path.push_back(par[i]);
}
reverse(path.begin(), path.end());
return path;
}
int getMinimumFuelCapacity(int X, int Y) {
ans=0;
vector<int> path=dijkstra(X, Y);
// for(auto x : path) cout << x << ' ';
// cout << endl;
int newAns=1e9;
for(int i=0; i<path.size(); i++) {
if(path[i] == X || path[i] == Y) {
if(adj[path[i]].size() > 2) {
if(adj[path[i]][2].first < ans) newAns=min(newAns, adj[path[i]][1].first);
else newAns=min(newAns, adj[path[i]][2].first);
}
} else {
bool f=false;
for(int j=0; j<adj[path[i]].size(); j++) {
if(!f && adj[path[i]][j].first == ans) f=true;
else {
newAns=min(newAns, adj[path[i]][j].first);
break;
}
}
}
}
//noUse.clear();
for(int i=1; i<path.size(); i++) {
noUse.insert({path[i], path[i-1]});
noUse.insert({path[i-1], path[i]});
}
int oldAns=ans;
ans=0;
dijkstra(X, Y); noUse.clear();
newAns=min(newAns, ans);
return max(newAns, oldAns);
}
