#define wiwihorz
#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ll long long int
#define pii pair<int, int>
#define INF 2000000000
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
int lg, n, ii, m;
vector<int> dep, par, rk, yes, ord, id, tag, deg;
vector<vector<int>> ac, mp;
int pos(int x) {
if(par[par[x]] == par[x]) return par[x];
else return par[x] = pos(par[x]);
}
void unite(int a, int b, int c) {
int aa = pos(a), bb = pos(b);
if(aa == bb) return;
if(rk[aa] < rk[bb]) swap(aa, bb);
rk[aa] += (rk[aa] == rk[bb]);
par[bb] = aa;
yes[aa] |= yes[bb];
id[aa] = c;
}
void build() {
ii = n - 1;
lg = 31 - __builtin_clz(n * 2);
mp.assign(n * 2, vector<int>());
ac.assign(lg + 1, vector<int>(n * 2, 0));
dep.assign(n * 2, 0);
id.assign(n, 0), iota(all(id), 0);
par.assign(n, 0), iota(all(par), 0);
rk.assign(n, 0);
yes.assign(n, 0);
ord.assign(m, 0), iota(all(ord), 0);
tag.assign(n * 2, -1);
deg.assign(n, 0);
}
void dfs(int x, int par, int d) {
dep[x] = d;
ac[0][x] = par;
for(auto i : mp[x]) if(i != par) {
dfs(i, x, d + 1);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
build();
sort(all(ord), [&](int a, int b) {
return W[a] < W[b];
});
for(auto i : ord) {
int a = U[i], b = V[i], c = W[i];
deg[a] ++;
deg[b] ++;
if(pos(a) == pos(b)) {
a = pos(a);
if(!yes[a]) {
yes[a] = 1;
tag[id[a]] = c;
}
}
else {
mp[++ii].push_back(id[pos(a)]);
mp[ii].push_back(id[pos(b)]);
unite(a, b, ii);
if(deg[a] > 2 || deg[b] > 2) yes[pos(a)] = 1;
if(yes[pos(a)]) tag[ii] = c;
}
}
dfs(ii, ii, 0);
rep(i, 1, lg) rep(j, 0, ii) {
ac[i][j] = ac[i - 1][ac[i - 1][j]];
}
}
int LCA(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int need = dep[a] - dep[b];
rep(i, 0, lg) if((need >> i) & 1) {
a = ac[i][a];
}
if(a == b) return a;
rrep(i, 0, lg) if(ac[i][a] != ac[i][b]) {
a = ac[i][a];
b = ac[i][b];
}
return ac[0][a];
}
int getMinimumFuelCapacity(int X, int Y) {
int lca = LCA(X, Y);
if(tag[lca] != -1) return tag[lca];
rrep(i, 0, lg) {
int to = ac[i][lca];
if(tag[to] == -1) lca = to;
}
return tag[ac[0][lca]];
}
