#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
// int extra = 9;
const int lg = 25;
vector <int> ad [maxn];
int deg[maxn];
int dad [maxn];
int val [maxn];
vector <bool> good (maxn, 0);
vector <int> cmp[maxn];
vector <int> depth (maxn);
int dg[maxn];
int up[maxn][lg];
void dfs (int u) {
for (auto v: cmp[u]) {
depth[v] = depth[u] + 1;
up[v][0] = u;
for (int i = 1; i < lg; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
dfs(v);
}
}
int lca (int x, int y) {
if (depth[x] < depth[y]) {
swap(x, y);
}
int k = depth[x] - depth[y];
for (int i = 0; i < lg; i++){
if (k & (1 << i)) {
x = up[x][i];
}
}
if (x == y) return x;
for (int i = lg - 1; i >= 0; i--) {
if (up[x][i] != up[y][i] || !good[up[x][i]]) {
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
int get_dad (int x) {
return dad[x] = (dad[x] == x ? x: get_dad(dad[x]));
}
void find (int u, vector <int> &nodes) {
nodes.push_back(u);
for (int v: cmp[u]) {
find(v, nodes);
}
}
bool propagate (int u) {
for (int v: ad[u]) {
good[u]= good[u] | propagate(v);
}
return good[u];
}
struct edg {
int x,y,cost;
};
bool comp (edg &a, edg &b) {
return a.cost < b.cost;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
vector <edg> eg;
good [maxn - 1] = 1;
for (int i = 0; i < maxn; i++){
dad[i] = i;
for (int j = 0; j < lg; j++){
up[i][j] = maxn - 1;
}
}
for (int i = 0; i < m; i++){
eg.push_back({u[i], v[i], w[i]});
}
sort(eg.begin(), eg.end(), comp);
for (auto &[u,v,cost]: eg) {
int p1 = get_dad(u);
int p2 = get_dad(v);
deg[u]++;
deg[v]++;
val[++extra] = cost;
dad[p1] = extra;
dad[p2] = extra;
cmp[extra].push_back(p1);
if (p1 != p2) cmp[extra].push_back(p2);
if (p1 == p2 || deg[u] >= 3 || deg[v] >= 3) {
good[extra] = 1;
}
}
for (int i = maxn - 1; i >= 0; i--){
if (!cmp[i].empty()) {
propagate(i);
dfs(i);
break;
}
}
}
int getMinimumFuelCapacity(int x, int y) {
int k = lca(x,y);
if (!good[k] || k == maxn - 1) return -1;
return val[k];
}
