#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 3> p3i;
namespace {
const int MXN = 300005, LG = 19;
int n, m;
vector<p3i> edges;
int deg[MXN];
struct DSU {
int p[MXN];
void init(int n) {
fill(p, p + n, -1);
}
int find(int x) {
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
void onion(int rt, int x) {
p[x] = rt;
}
} dsu;
namespace TREE {
vector<int> edge[MXN];
int val[MXN];
bitset<MXN> tag;
int p[LG][MXN], d[MXN];
void ADD_EDGE(int x, int y) {
edge[x].push_back(y);
edge[y].push_back(x);
}
void CONSTRUCT() {
sort(edges.begin(), edges.end());
dsu.init(n + m);
FOR(i, 0, m) {
auto [w, u, v] = edges[i];
deg[u]++;
deg[v]++;
int uu = dsu.find(u), vv = dsu.find(v);
int now = i + n;
debug(now, u, v, uu, vv);
val[now] = w;
if (uu == vv) {
tag[now] = true;
dsu.onion(now, uu);
ADD_EDGE(now, uu);
} else {
tag[now] = ((tag[uu]) | (tag[vv]) | (deg[u] >= 3) | (deg[v] >= 3));
dsu.onion(now, uu);
dsu.onion(now, vv);
ADD_EDGE(now, uu);
ADD_EDGE(now, vv);
}
}
}
void DFS(int id, int par, int dep) {
p[0][id] = par;
d[id] = dep;
for (auto &i : edge[id]) {
if (i == par) continue;
DFS(i, id, dep + 1);
}
}
void BUILD() {
CONSTRUCT();
DFS(n + m - 1, n + m - 1, 0);
// FOR(i, 0, n + m) {
// for (auto &j : edge[i]) cout << j << ' ';
// cout << '\n';
// }
// FOR(i, 0, n + m) cout << p[0][i] << ' ';
// cout << '\n';
// FOR(i, 0, n + m) cout << tag[i] << ' ';
// cout << '\n';
// cout << "---\n";
FOR(w, 1, LG) {
FOR(i, 0, n + m) {
p[w][i] = p[w - 1][p[w - 1][i]];
}
}
}
int LEAP(int x, int k) {
FOR(w, 0, LG) if (k & (1 << w)) x = p[w][x];
return x;
}
int LCA(int x, int y) {
if (d[x] < d[y]) swap(x, y);
x = LEAP(x, d[x] - d[y]);
if (x == y) return x;
for (int w = LG - 1; w >= 0; w--) {
if (p[w][x] == p[w][y]) continue;
x = p[w][x];
y = p[w][y];
}
return p[0][x];
}
int BSH(int x) {
if (tag[x]) return x;
for (int w = LG - 1; w >= 0; w--) {
if (tag[p[w][x]]) continue;
x = p[w][x];
}
return p[0][x];
}
int SOLVE(int x, int y) {
int lca = LCA(x, y);
debug(x, y, lca);
int ans = BSH(lca);
if (!tag[ans]) return -1;
return val[ans];
}
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
FOR(i, 0, m) edges.push_back(p3i{W[i], U[i], V[i]});
TREE::BUILD();
}
int getMinimumFuelCapacity(int X, int Y) {
return TREE::SOLVE(X, Y);
}
