#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 2e9
const int N = 1e5;
vector<pair<int,int>> g[N];
multiset<int> st;
int wt[N];
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
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]});
wt[v[i]] = w[i];
st.insert(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);
pq.push({0, s});
dist[s] = 0;
vector<int> p(N);
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};
}
int getMinimumFuelCapacity(int a, int b){
if(a > 0) st.erase(st.find(wt[a]));
if(b > 0) st.erase(st.find(wt[b]));
int rtn = ((a == 0 or b == 0) ? (st.size() <= 1 ? -1 : *next(st.begin())) : (st.empty() ? -1 : *st.begin()));
if(a > 0) st.insert(wt[a]);
if(b > 0) st.insert(wt[b]);
if(a > 0) rtn = max(rtn, wt[a]);
if(b > 0) rtn = max(rtn, wt[b]);
return rtn;
auto [dist, p] = dijkstra(a);
int mn = inf, v = p[b], pv = b;
while(v != a){
for(auto [ch, w] : g[v]){
if(ch != pv and ch != p[v]) mn = min(mn, w);
}
pv = v;
v = p[v];
}
auto [dist1, p1] = dijkstra(a, {a, pv});
mn = min(mn, dist1[b]);
auto [dist2, p2] = dijkstra(b, {b, p[b]});
mn = min(mn, dist2[a]);
int ans = max(dist[b], mn);
return ans == inf ? -1 : ans;
}
