#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 2e9
const int N = 1e5;
vector<pair<int,int>> g[N];
int n, m;
void init(int n_, int m_, vector<int> u, vector<int> v, vector<int> w){
n = n_, m = m_;
for(int i=0; i<m; i++){
g[u[i]].push_back({v[i], w[i]});
g[v[i]].push_back({u[i], w[i]});
}
}
pair<vector<int>, vector<int>> dijkstra(int s, pair<int,int> pr = {-1, -1}){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> dist(n, inf), p(n);
pq.push({0, s});
dist[s] = 0;
p[s] = s;
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(d > dist[v]) continue;
for(auto [ch, w] : g[v]){
if(make_pair(v, ch) == pr or make_pair(ch, v) == pr) continue;
int nw = max(d, w);
if(nw < dist[ch]){
dist[ch] = nw;
p[ch] = v;
pq.push({dist[ch], ch});
}
}
}
return {dist, p};
}
bool cmp(pair<int,int> p1, pair<int,int> p2){
return p1.second < p2.second;
}
int getMinimumFuelCapacity(int a, int b){
auto [dist1, p1] = dijkstra(a);
auto [dist2, p2] = dijkstra(b);
auto [dist, p] = dijkstra(a, {a, p2[a]});
int ans = dist[b];
for(int i=0; i<n; i++){
if(g[i].size() < 3) continue;
sort(g[i].begin(), g[i].end(), cmp);
int mx = 0, c = 0;
for(auto [ch, w] : g[i]){
if(ch == p1[i] or ch == p2[i]) mx = max(mx, w), c++;
}
for(auto [ch, w] : g[i]){
if(c < 3 and ch != p1[i] and ch != p2[i]) mx = max(mx, w), c++;
}
ans = min(ans, max(max(dist1[i], dist2[i]), mx));
}
return ans == inf ? -1 : ans;
}
