#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e6 + 7;
const int LG = 18;
const int MOD = 998244353;
const int INF = (int)1e18 + 7;
int n, m, t, flag, k, u, v, w, ans, ans2, tmp, tmp2, tmp3, tmp4, q, timer;
int arr[MAXN], num[MAXN];
int par[MAXN], love[MAXN], dp[MAXN], deg[MAXN];
int h[MAXN], dad[MAXN], pow2dad[MAXN][LG];
vector<pair<int, pii> > edge;
vector<int> adj[MAXN];
/* DSU */
inline int get_par(int v) {
return (par[v] == v? v : par[v] = get_par(par[v]));
}
void unite(int u, int v, int w) {
int u2, v2;
u2 = u;
v2 = v;
deg[u2]++, deg[v2]++;
u = get_par(u), v = get_par(v);
if (u == v) {
if (!love[u]) {
love[u] = 1;
num[u] = w;
}
} else {
par[u] = par[v] = flag;
par[flag] = flag;
adj[flag].pb(u), adj[flag].pb(v);
num[flag] = w;
if (love[u] || love[v]) {
love[flag] = 1;
} else {
love[flag] = (deg[u2] == 3 || deg[v2] == 3);
}
// cout << "@" << flag << " " << u << " " << v << endl;
flag++;
}
}
/* DSU */
/* LCA */
inline int up(int v, int k) {
for (int i=LG-1; i>=0; i--) {
if ((1<<i) <= k) {
k -= (1<<i);
v = pow2dad[v][i];
}
}
return v;
}
int LCA(int u, int v) {
if (h[u] < h[v]) swap(u, v);
u = up(u, h[u]-h[v]);
for (int i=LG-1; i>=0; i--) {
if (h[v] >= (1<<i) && pow2dad[v][i] != pow2dad[u][i]) {
v = pow2dad[v][i];
u = pow2dad[u][i];
}
}
if (u == v) return u;
return dad[v];
}
/* LCA */
// void DFS(int v) {
// for (int u:adj[v]) {
// if (u != dad[v]) {
// dad[u] = v;
// h[u] = h[v]+1;
// DFS(u);
// love[v] |= love[u];
// }
// }
// dp[v] = (love[v]? v : dp[dad[v]]);
// }
void DFS(int v) {
dp[v] = (love[v]? v : dp[dad[v]]);
for (int u:adj[v]) {
if (u != dad[v]) {
dad[u] = v;
h[u] = h[v]+1;
DFS(u);
}
}
}
void DFS2(int v) {
dp[v] = (love[v]? v : dp[dad[v]]);
for (int u:adj[v]) if (u != dad[v]) DFS2(u);
}
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++) {
// cin >> u >> v >> w;
u = U[i]+1;
v = V[i]+1;
w = W[i];
edge.pb(mp(w, mp(u, v)));
}
sort(all(edge));
flag = n+1;
for (int i=1; i<=n; i++) par[i] = i;
for (int i=0; i<m; i++) unite(edge[i].S.F, edge[i].S.S, edge[i].F);
flag--;
DFS(flag);
// DFS2(flag);
for (int i=1; i<=flag; i++) pow2dad[i][0] = dad[i];
for (int j=1; j<LG; j++) for (int i=1; i<=flag; i++) pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];
num[0]--;
}
int getMinimumFuelCapacity(int X, int Y) {
return num[dp[LCA(X+1, Y+1)]];
}
