#include<bits/stdc++.h>
using namespace std;
#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))
template<class T> bool minimize(T& a, T b){
if(a > b) return a = b, true;
return false;
}
template<class T> bool maximize(T& a, T b){
if(a < b) return a = b, true;
return false;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N = 3e5 + 5;
struct edge{
int u, v, w;
bool operator < (const edge& o){
return w < o.w;
}
};
int n, m, q, nNodes, par[N], h[N], lift[20][N], weight[N], deg[N], lab[N];
bool good[N];
vector<int> adj[N];
vector<edge> edges;
int root(int u){
return par[u] == u ? u : (par[u] = root(par[u]));
}
void addEdge(int u, int v, int w, int maxDeg){
u = root(u), v = root(v);
par[u] = nNodes;
par[v] = nNodes;
weight[nNodes] = w;
good[nNodes] = good[u] || good[v];
adj[nNodes].push_back(u);
if(u == v) good[nNodes] = true;
else{
adj[nNodes].push_back(v);
if(maxDeg > 2) good[nNodes] = true;
}
++nNodes;
}
void dfsLCA(int u){
for(int v : adj[u]){
h[v] = h[u] + 1;
lift[0][v] = u;
for(int i = 1; i <= 18; ++i){
lift[i][v] = lift[i - 1][lift[i - 1][v]];
}
dfsLCA(v);
}
}
int getLCA(int u, int v){
if(h[u] != h[v]){
if(h[u] < h[v]) swap(u, v);
for(int i = 18; i >= 0; --i){
if(h[u] - (1 << i) >= h[v]){
u = lift[i][u];
}
}
}
if(u == v) return u;
for(int i = 18; i >= 0; --i){
if(lift[i][u] != lift[i][v]){
u = lift[i][u];
v = lift[i][v];
}
}
return lift[0][u];
}
int findFirstGood(int u){
if(good[u]) return u;
for(int i = 18; i >= 0; --i){
if(lift[i][u] != -1 and !good[lift[i][u]]){
u = lift[i][u];
}
}
if(!good[lift[0][u]]) return -1;
return lift[0][u];
}
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.push_back({U[i], V[i], W[i]});
}
memset(lift, -1, sizeof(lift));
sort(range(edges));
iota(par, par + n + m, 0);
nNodes = n;
for(int i = 0; i < m; ++i){
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
++deg[u]; ++deg[v];
addEdge(u, v, w, max(deg[u], deg[v]));
}
dfsLCA(nNodes - 1);
}
int getMinimumFuelCapacity(int X, int Y){
int mid = findFirstGood(getLCA(X, Y));
if(mid == -1) return -1;
else return weight[mid];
}
