//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5e5+100;
int dsu[MAXN], deg[MAXN], we[MAXN];
vector<int> g[MAXN];
bool dsu_c[MAXN], c[MAXN];
void init(int n){
rep(i, 0, n){
dsu[i] = i, dsu_c[i] = false, c[i] = false;
}
}
int find(int x){
if(x == dsu[x]) return x;
dsu_c[dsu[x]] |= dsu_c[x];
dsu[x] = find(dsu[x]);
return dsu[x];
}
int root;
void unite(int a, int b, int w){
a = find(a); b = find(b);
dsu_c[root] = c[root] = (dsu_c[a] || dsu_c[b] || (a == b));
we[root] = w;
dsu[a] = root;
g[root].pb(a);
if(a != b){
dsu[b] = root;
g[root].pb(b);
}
root++;
}
const int MAXK = 20+5;
int dep[MAXN], p[MAXK][MAXN];
void dfs(int v, int pa){
p[0][v] = pa;
for(int u : g[v]){
dep[u] = dep[v] + 1;
dfs(u, v);
}
}
struct Edge{
int u, v, w;
bool operator<(const Edge& oth) const{
return w < oth.w;
}
};
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
vector<Edge> e;
rep(i, 0, M){
e.pb({U[i], V[i], W[i]});
}
sort(all(e));
root = N;
init(N + M);
rep(i, 0, M){
auto [u, v, w] = e[i];
deg[u]++, deg[v]++;
if(deg[u] >= 3) dsu_c[u] = true;
if(deg[v] >= 3) dsu_c[v] = true;
unite(u, v, w);
}
rep(i, 0, N + M){
if(find(i) == i)
dfs(i, -1);
}
rep(k, 0, MAXK - 1){
rep(i, 0, N + M){
if(p[k][i] != -1){
p[k + 1][i] = p[k][p[k][i]];
} else{
p[k + 1][i] = -1;
}
}
}
}
int query(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
per(k, MAXK - 1, 0){
if(diff >> k & 1){
u = p[k][u];
}
}
if(u == v && c[u]) return we[u];
per(k, MAXK - 1, 0){
if(p[k][u] != -1 && (p[k][u] != p[k][v] || !c[p[k][u]])){
u = p[k][u], v = p[k][v];
}
}
if(p[0][u] == -1) return -1;
return we[p[0][u]];
}
int getMinimumFuelCapacity(int X, int Y){
return query(X, Y);
}
