#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 100000;
const int LOG = 17;
const int INF = 1000000007;
int val[N+5][LOG+1];
int par[N+5][LOG+1];
vector <pair <int, int>> graf[N+5];
int tjm;
int in[N+5], out[N+5];
void dfs(int v, int p, int d){
in[v] = ++tjm;
par[v][0] = p;
val[v][0] = d;
for(int j=1; j<=LOG; j++){
par[v][j] = par[par[v][j-1]][j-1];
val[v][j] = max(val[v][j-1], val[par[v][j-1]][j-1]);
}
for(auto pr : graf[v]) if(pr.first != p) dfs(pr.first, v, pr.second);
out[v] = tjm;
}
int moze[N+5];
int deg[N+5];
vector <int> vec[N+5];
int comp[N+5];
bool ima[N+5];
void init(int n, int m, vector <int> U, vector <int> V, vector <int> W) {
for(int i=1; i<=n; i++) moze[i] = INF, comp[i] = i, vec[i].push_back(i);
vector <tuple <int, int, int>> edges;
for(int i=0; i<m; i++){
int a = U[i] + 1;
int b = V[i] + 1;
int c = W[i];
edges.push_back({c, a, b});
}
sort(edges.begin(), edges.end());
for(auto e : edges){
int c, a, b;
tie(c, a, b) = e;
if(comp[a] == comp[b]){
if(ima[comp[a]]) continue;
ima[comp[a]] = 1;
for(auto x : vec[comp[a]]) moze[x] = c;
continue;
}
graf[a].push_back({b, c});
graf[b].push_back({a, c});
bool novi = 0;
deg[a]++;
deg[b]++;
if(deg[a] >= 3 || deg[b] >= 3) novi = 1;
a = comp[a];
b = comp[b];
if(vec[a].size() < vec[b].size()) swap(a, b);
if(!ima[a] && (novi || ima[b])){
ima[a] = 1;
for(auto x : vec[a]) moze[x] = c;
}
if(!ima[b] && (novi || ima[a])){
ima[b] = 1;
for(auto x : vec[b]) moze[x] = c;
}
for(auto x : vec[b]) comp[x] = a, vec[a].push_back(x);
vec[b].clear();
}
dfs(1, 0, 0);
}
bool is_parent(int a, int b){ return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]); }
int query(int x, int y){
int res = 0;
for(int j=LOG; j>=0; j--) if(!is_parent(par[x][j], y)) res = max(res, val[x][j]), x = par[x][j];
if(!is_parent(x, y)) res = max(res, val[x][0]);
for(int j=LOG; j>=0; j--) if(!is_parent(par[y][j], x)) res = max(res, val[y][j]), y = par[y][j];
if(!is_parent(y, x)) res = max(res, val[y][0]);
return res;
}
int getMinimumFuelCapacity(int x, int y) {
x++;
y++;
int g = max(query(x, y), moze[x]);
return (g == INF ? -1 : g);
}
