#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using ll = long long;
const int mxN = 3e5+10;
int p[mxN], deg[mxN], pos[mxN];
int mx[mxN][22], anc[mxN][22];
int w[mxN], dep[mxN];
vector<int> adj[mxN];
int get(int x) {
return p[x] == x ? x : p[x] = get(p[x]);
}
void uni(int a, int b, int k, bool can) {
if(pos[a] || pos[b]) can = true;
p[a] = p[b] = p[k] = k;
pos[k] = can;
adj[k].push_back(a); if(a != b) adj[k].push_back(b);
}
void dfs(int node, int p) {
anc[node][0] = p;
for(int j = 1; j <= 20; j++) {
anc[node][j] = anc[anc[node][j-1]][j-1];
}
mx[node][0] = (pos[p] ? w[p] : 0);
for(int j = 1; j <= 20; j++) {
if(mx[node][j-1] != 0) mx[node][j] = mx[node][j-1];
else mx[node][j] = mx[anc[node][j-1]][j-1];
}
for(auto it : adj[node]) {
dep[it] = dep[node]+1;
dfs(it, node);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
iota(p, p+N+M+1, 0); int n = N;
int cnt = n;
vector<int> ord(M); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
return W[a] < W[b];
});
for(int i = 0; i < M; i++) {
int u = U[ord[i]], v = V[ord[i]];
w[cnt] = W[ord[i]];
++deg[u]; ++deg[v];
bool can = false;
if(deg[u] >= 3 || deg[v] >= 3) can = true;
u = get(u); v = get(v);
if(u == v) can = true;
uni(u, v, cnt, can); ++cnt;
}
--cnt;
dfs(cnt, cnt);
}
void jmp(int &a, int k) {
for(int j = 20; j >= 0; j--) {
if(k & (1 << j)) a = anc[a][j];
}
}
int LCA(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
jmp(a, dep[a]-dep[b]);
if(a == b) return a;
for(int k = 20; k >= 0; k--) {
if(anc[a][k] != anc[b][k]) {
a = anc[a][k];
b = anc[b][k];
}
}
return anc[a][0];
}
int getMinimumFuelCapacity(int X, int Y) {
int l = LCA(X, Y);
if(pos[l]) return w[l];
for(int k = 0; k <= 20; k++) {
if(mx[l][k] != 0) return mx[l][k];
}
return -1;
}
