//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int INF = 1e9, nax = 100 * 1000 + 10;
vector<tuple<int, int, int>> edges;
int p[nax * 3], ed[nax * 3], leaves[nax * 3], sz[nax * 3];
int cost[nax * 3];
bool good[3 * nax];
int deg[nax], nxt;
int Fund(int x) {
if(p[x] != x) {
p[x] = Fund(p[x]);
}
return p[x];
}
vi G[3 * nax];
void Onion(int a, int b, int w) {
int pa = Fund(a), pb = Fund(b);
if(pa == pb) {
p[pa] = nxt;
p[nxt] = nxt;
G[nxt].PB(pa);
leaves[nxt] = leaves[pa], good[nxt] = good[pa], ed[nxt] = ed[pa];
sz[nxt] = sz[pa];
} else {
p[pa] = nxt, p[pb] = nxt;
p[nxt] = nxt;
G[nxt].PB(pa);
G[nxt].PB(pb);
leaves[nxt] = leaves[pa] + leaves[pb];
good[nxt] = good[pa] | good[pb];
ed[nxt] = ed[pa] + ed[pb];
sz[nxt] = sz[pa] + sz[pb];
}
if(deg[a] == 1) leaves[nxt]--;
else if(deg[a] == 0) leaves[nxt]++;
if(deg[b] == 1) leaves[nxt]--;
else if(deg[b] == 0) leaves[nxt]++;
deg[a]++, deg[b]++;
ed[nxt]++;
if(ed[nxt] >= sz[nxt]) {
good[nxt] = 1;
} else if(leaves[nxt] > 2) {
good[nxt] = 1;
}
cost[nxt] = w;
nxt++;
}
int par[3 * nax][19];
int dep[3 * nax];
void dfs(int x, int pr) {
par[x][0] = pr;
//cerr << x << ": " << good[x] << "\n";
for(int y : G[x]) {
//cerr << x << " -> " << y << "\n";
dep[y] = dep[x] + 1;
dfs(y, x);
}
}
void init(int n, int m, vi U, vi V, vi W) {
for(int i = 0; i < n; ++i) {
p[i] = i;
sz[i] = 1;
leaves[i] = 0;
ed[i] = deg[i] = 0;
}
for(int i = 0; i < m; ++i) {
edges.emplace_back(W[i], U[i], V[i]);
}
sort(edges.begin(), edges.end());
nxt = n;
for(auto [w, u, v] : edges) {
Onion(u, v, w);
}
nxt--;
dfs(nxt, 0);
par[nxt][0] = nxt;
for(int step = 1; step < 19; ++step) {
for(int i = 0; i <= nxt; ++i) {
par[i][step] = par[par[i][step - 1]][step - 1];
}
}
}
int lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
for(int i = 18; i >= 0; --i) {
if(dep[par[y][i]] >= dep[x]) {
y = par[y][i];
}
}
if(x == y) return x;
for(int i = 18; i >= 0; --i) {
if(par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
int getMinimumFuelCapacity(int x, int y) {
int z = lca(x, y);
//cerr << "Z: " << z << "\n";
if(good[z]) return cost[z];
for(int i = 18; i >= 0; --i) {
if(!good[par[z][i]]) {
z = par[z][i];
}
}
z = par[z][0];
if(!good[z]) {
return -1;
} else {
return cost[z];
}
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
//cout << getMinimumFuelCapacity(1, 2) << "\n";
//cout << getMinimumFuelCapacity(2, 4) << "\n";
//cout << getMinimumFuelCapacity(0, 1) << "\n";
//}
