#include "swap.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef pair<int,int> ii;
const int inf = 1023456789;
int n, newNode;
namespace ufds{
int p[200005];
void init(){
for(int i = 0;i < 2*n;i++) p[i] = i;
}
int findSet(int u){
if(u == p[u]) return u;
else return p[u] = findSet(p[u]);
}
bool unionSet(int u, int v){
u = findSet(u), v = findSet(v);
if(u == v) return false;
if(u > v) swap(u, v);
p[u] = v;
return true;
}
}
struct edge{ int u, v, w; };
vector<edge> edges;
int maxEdge[200005];
int minWork[200005];
int L[200005];
int R[200005];
int deg[200005];
int p[200005][19];
int depth[200005];
void dfs0(int u){
if(L[u] == R[u] && L[u] == 0) return;
depth[L[u]] = depth[u] + 1;
depth[R[u]] = depth[u] + 1;
dfs0(L[u]); dfs0(R[u]);
}
void dfs1(int u){
if(L[u] == R[u] && L[u] == 0) return;
dfs1(L[u]); dfs1(R[u]);
minWork[u] = min(minWork[u], minWork[L[u]]); ///pass up to parent
minWork[u] = min(minWork[u], minWork[R[u]]);
}
void dfs2(int u){
if(L[u] == R[u] && L[u] == 0) return;
minWork[L[u]] = min(minWork[u], minWork[L[u]]); ///pass down to children
minWork[R[u]] = min(minWork[u], minWork[R[u]]);
dfs2(L[u]); dfs2(R[u]);
}
int LCA(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
for(int k = 18;k >= 0;k--){
int newU = p[u][k];
if(depth[newU] >= depth[v]) u = newU;
}
for(int k = 18;k >= 0;k--){
int newU = p[u][k], newV = p[v][k];
if(newU != newV){
u = newU;
v = newV;
}
}
return p[u][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N; newNode = n;
for(int i = 0;i < M;i++) edges.push_back({U[i], V[i], W[i]});
ufds::init();
fill(minWork, minWork+2*n, inf);
sort(all(edges), [&](edge a, edge b){ return a.w < b.w; });
vector<edge> cycle;
for(edge e : edges){
deg[e.u]++;
deg[e.v]++;
if(deg[e.u] >= 3) minWork[e.u] = min(e.w, minWork[e.u]);
if(deg[e.v] >= 3) minWork[e.v] = min(e.w, minWork[e.v]);
int u = ufds::findSet(e.u), v = ufds::findSet(e.v);
if(u != v){
L[newNode] = u;
R[newNode] = v;
ufds::unionSet(newNode, u);
ufds::unionSet(newNode, v);
maxEdge[newNode] = e.w;
p[u][0] = newNode;
p[v][0] = newNode;
newNode++;
}
else cycle.push_back(e);
}
n = newNode;
p[n-1][0] = -1;
for(int k = 1;k <= 18;k++){
for(int i = 0;i < n;i++){
if(p[i][k-1] == -1) p[i][k] = -1;
else p[i][k] = p[p[i][k-1]][k-1];
}
}
dfs0(n-1);
for(edge e : cycle){
int u = e.u, v = e.v;
int lca = LCA(u, v);
minWork[lca] = min(e.w, minWork[lca]);
}
dfs1(n-1);
for(int i = 0;i < n;i++) minWork[i] = max(minWork[i], maxEdge[i]);
dfs2(n-1);
}
int getMinimumFuelCapacity(int X, int Y){
int lca = LCA(X, Y);
//cout << X << " " << Y << " " << lca << "\n";
int ans = max(minWork[lca], maxEdge[lca]);
if(ans == inf) ans = -1;
return ans;
}
