#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 400004;
int N, M, R[MAX], D[MAX], H[MAX], S[MAX], P[19][MAX];
bool T[MAX], C[MAX], isLine;
vector<tuple<int, int, int>> E;
vector<int> G[MAX];
int Find(int n) {
if (n == R[n]) return n;
return R[n] = Find(R[n]);
}
void DFS(int cur, int prev) {
H[cur] = H[prev] + 1;
P[0][cur] = prev;
for (int next : G[cur]) DFS(next, cur);
}
int LCA(int a, int b) {
if (H[a] > H[b]) swap(a, b);
for (int i = 18; i >= 0; --i) if ((H[b] - H[a]) & (1 << i)) b = P[i][b];
if (a == b) return a;
for (int i = 18; i >= 0; --i) if (P[i][a] != P[i][b]) a = P[i][a], b = P[i][b];
return P[0][a];
}
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) {
E.emplace_back(W[i], U[i], V[i]);
D[U[i]]++;
D[V[i]]++;
}
if (N == M + 1 && *max_element(D, D + MAX) <= 2) isLine = 1;
sort(E.begin(), E.end());
iota(R, R + MAX, 0);
memset(D, 0, sizeof(D));
int node = N;
for (auto [w, a, b] : E) {
int ra = Find(a), rb = Find(b);
S[node] = w;
T[node] = (T[ra] || T[rb] || ++D[a] >= 3 || ++D[b] >= 3);
C[node] = (C[ra] || C[rb] || ra == rb);
G[node].push_back(ra);
if (ra != rb) G[node].push_back(rb);
R[ra] = R[rb] = node;
node++;
}
DFS(node - 1, node - 1);
for (int n = 1; n < 19; ++n) for (int i = 0; i < node; ++i) P[n][i] = P[n - 1][P[n - 1][i]];
}
int getMinimumFuelCapacity(int x, int y) {
if (isLine) return -1;
int c = LCA(x, y);
for (int i = 18; i >= 0; --i) {
int p = P[i][c];
if (!T[p] && !C[p]) c = p;
}
if (!T[c] && !C[c]) c = P[0][c];
return S[c];
}
