#include <bits/stdc++.h>
#ifndef LOCAL
#include "swap.h"
#endif // LOCAL
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct DSU {
vector<int> lab, contain, id;
int counter;
DSU (int sz) : lab(sz + 1, -1), contain(sz + 1),
id(sz + 1), counter(sz) { iota(all(id), 0); }
int get (int u) {
if (lab[u] < 0) return u;
return lab[u] = get(lab[u]);
}
int getID (int u) { return id[get(u)]; }
bool good (int u) { return contain[get(u)]; }
bool unite (int a, int b) {
a = get(a), b = get(b);
if (a == b)
return contain[a] = 1, id[a] = ++counter, 0;
if (-lab[a] < -lab[b]) swap(a, b);
lab[a] += lab[b], lab[b] = a;
contain[a] |= contain[b], id[a] = ++counter;
return 1;
}
void setNode (int u) { contain[get(u)] = 1; }
};
const int mn = 3e5 + 5;
int up[mn][20], curDeg[mn], depth[mn], weight[mn], n, m;
bool good[mn], vis[mn];
vector<int> adj[mn];
vector<tpl> edges;
void dfs (int u, int p, int d) {
up[u][0] = p, depth[u] = d;
for (int i = 1; i < 20; i++)
up[u][i] = up[up[u][i - 1]][i - 1];
for (int v : adj[u]) dfs(v, u, d + 1);
}
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++)
edges.emplace_back(W[i], U[i] + 1, V[i] + 1);
sort(all(edges));
/// build kruskal reconstruction tree
DSU dsu(n);
for (int i = 0; i < m; i++) {
int a, b, c; tie(c, a, b) = edges[i];
int u = dsu.getID(a), v = dsu.getID(b);
if (!u) cout << "troi oi " << a << endl;
if (!v) cout << "troi oi " << b << endl;
// mark special nodes
if (++curDeg[a] == 3) dsu.setNode(a);
if (++curDeg[b] == 3) dsu.setNode(b);
// merge component
bool connected = dsu.unite(a, b);
int cur = dsu.getID(a);
adj[cur].push_back(u);
if (connected)
adj[cur].push_back(v);
weight[cur] = c, good[cur] = dsu.good(a);
}
weight[0] = -1, good[0] = 1;
// for (int i = 1; i <= n + m; i++) {
// cout << "node " << i << ": ";
// for (int j : adj[i]) cout << j << " ";
// cout << "\n";
// }
/// run dfs
for (int i = 1; i <= n; i++) {
int u = dsu.getID(i);
if (!vis[u]) dfs(u, 0, 0), vis[u] = 1;
}
}
int goUp (int a, int k) {
for (int i = 0; k; i++, k >>= 1)
if (k & 1) a = up[a][i];
return a;
}
int lca (int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = goUp(a, depth[a] - depth[b]);
if (a == b && good[a]) return a;
for (int i = 19; i >= 0; i--)
if (up[a][i] != up[b][i] || !good[up[a][i]]) a = up[a][i], b = up[b][i];
return up[a][0];
}
int getMinimumFuelCapacity (int X, int Y) {
return weight[lca(X + 1, Y + 1)];
}
