#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int maxn = 3e5+5;
const int LOG = 20;
int rep[maxn], C[maxn], deg[maxn], dp[maxn], ok[maxn], G[maxn], d[maxn], n, m, N, up[maxn][LOG];
vector<int> adj[maxn];
vector<array<int, 3>> A;
int find(int x){
if(x == rep[x])
return x;
return rep[x] = find(rep[x]); // path compression
}
void merge(int a, int b) {
a = find(a), b = find(b), n++;
if(a == b)
C[n] = 1;
rep[n] = rep[a] = rep[b] = n;
if(G[a] or G[b])
G[n] = 1;
if(C[a] or C[b])
C[n] = 1;
adj[n].pb(a);
if(a != b)
adj[n].pb(b);
}
void dfs(int x, int pr = -1) {
for(int i = 1; i < LOG; ++i)
up[x][i] = up[up[x][i-1]][i-1];
if(ok[x])
pr = x;
dp[x] = pr;
for(int &i : adj[x]) {
d[i] = d[x]+1;
up[i][0] = x;
dfs(i, pr);
}
}
int LCA(int a, int b) {
if(d[a] < d[b])
swap(a, b);
int diff = d[a]-d[b];
for(int i = LOG-1; i >= 0; --i)
if(diff>>i&1)
a = up[a][i];
if(a == b)
return a;
for(int i = LOG-1; i >= 0; --i)
if(up[a][i] != up[b][i])
a = up[a][i], b = up[b][i];
return up[a][0];
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
n = _N, N = _N, m = _M;
for(int i = 1; i <= n+m; ++i)
rep[i] = i;
for(int i = 0; i < m; ++i)
A.pb({W[i], U[i]+1, V[i]+1});
sort(all(A));
for(auto &[w, u, v] : A){
deg[u]++, deg[v]++;
if(deg[u] >= 3 or deg[v] >= 3)
G[n+1] = 1;
merge(u, v);
}
for(int i = 1; i <= n; ++i)
ok[i] = (G[i] or C[i]);
dfs(n);
}
int getMinimumFuelCapacity(int x, int y) {
x++, y++;
int ad = LCA(x, y);
if(dp[ad] == -1)
return -1;
if(dp[ad]-N-1 <= 0)
return -1;
return A[dp[ad]-N-1][0];
}
