#include "swap.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 300005;
int pardsu[nmax], last, lca[nmax][20], marked[nmax], grad[nmax], val[nmax], timp, in[nmax], out[nmax], apropiat[nmax], ans[nmax], sub[nmax];
vector<pair<int, pair<int,int>>>edges;
vector<int>nod[nmax];
int findpar(int x){
if(x != pardsu[x]){
pardsu[x] = findpar(pardsu[x]);
}
return pardsu[x];
}
void dfs(int s, int apr, int par = 0){
in[s] = ++timp;
if(sub[s]) apr = val[s];
ans[s] = apr;
for(auto it : nod[s]){
dfs(it, apr, s);
}
out[s] = ++timp;
}
bool is_lca(int x, int y){
if(in[x] <= in[y] && out[x] >= out[y]) return true;
else return false;
}
void dfs1(int s){
if(marked[s]) sub[s]++;
for(auto it : nod[s]){
dfs1(it);
sub[s] += sub[it];
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
last = N;
for(int i=1;i<=N;i++) pardsu[i] = i;
for(int i=1;i<=N;i++) val[i] = 1e9;
for(int i=0;i<M;i++){
U[i]++; V[i]++;
edges.push_back({W[i], {U[i], V[i]}});
}
sort(all(edges));
for(auto it : edges){
int x = findpar(it.sc.fr);
int y = findpar(it.sc.sc);
++last;
pardsu[y] = last;
pardsu[x] = last;
pardsu[last] = last;
val[last] = it.fr;
grad[it.sc.sc]++;
grad[it.sc.fr]++;
lca[x][0] = last;
lca[y][0] = last;
nod[last].push_back(x);
if(x != y) nod[last].push_back(y);
if(x == y){
marked[last] = 1;
}
else{
if(grad[it.sc.sc] >= 3 || grad[it.sc.fr] >= 3){
marked[last] = 1;
}
}
}
for(int i=1;i<=19;i++){
for(int j=1;j<=last;j++){
lca[j][i] = lca[lca[j][i-1]][i-1];
}
}
dfs1(last);
dfs(last, 1e9);
// for(int i=1;i<=N+M;i++) cout << ans[i] << ' ';
// cout << '\n';
}
int getMinimumFuelCapacity(int X, int Y) {
X++;
Y++;
int curr;
if(is_lca(X, Y)) curr = X;
else if(is_lca(Y, X)) curr = Y;
else{
curr = X;
for(int i=19;i>=0;i--){
if(lca[curr][i] != 0 && !is_lca(lca[curr][i], Y)) curr = lca[curr][i];
}
curr = lca[curr][0];
}
if(ans[curr] < 1e9){
return ans[curr];
}
else{
return -1;
}
}
/**
6 5
0 1 1
1 2 2
1 3 3
1 4 4
4 5 5
3
0 4
5 4
0 2
*/
