#include "swap.h"
#include<bits/stdc++.h>
#include <vector>
#define pb push_back
using namespace std;
const int N = 1e6 + 5;
vector<pair<int, int> > g[N];
int mx, n, m;
bool sb2 = 1;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
for(int i = 0; i < M; ++i){
int u = U[i], v = V[i], w = W[i];
if(u != 0 and v != 0)
sb2 = false;
g[u].pb({w, v});
g[v].pb({w, u});
mx = max(mx, w);
}
for(int i = 0; i < n; ++i)
sort(g[i].begin(), g[i].end());
}
int getMinimumFuelCapacity(int X, int Y) {
if(sb2 and m == n - 1){
if(n <= 3) return -1;
if(X == 0){
int x = g[Y][0].second, xx, dest, mn;
if(g[0][0].second != Y){
xx = g[0][0].first;
dest = g[0][0].second;
}else{
xx = g[0][1].first;
dest = g[0][1].second;
}
if(g[0][1].second != Y and g[0][1].second != dest)
mn = g[0][1].first;
else
mn = g[0][2].first;
return max({x, xx, mn});
}
int x = g[X][0].second, xx = g[Y][0].second, mn;
if(g[0][0].second != X and g[0][0].second != Y)
mn = g[0][0].first;
else if(g[0][1].second != X and g[0][1].second != Y)
mn = g[0][1].first;
else
mn = g[0][2].first;
return max({x, xx, mn});
}
if(m == n - 1)
return -1;
else
return mx;
}
