#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = (int)5e5+10;
const int lgn = 20;
int n, m, num;
int jmp[lgn][maxn];
vector<int> adj[maxn];
int p[maxn], lev[maxn], wei[maxn], line[maxn], good[maxn];
struct Edge{ int u, v, w, i; };
Edge edge[maxn];
int getPath(int x, int steps){
for(int i = lgn-1; i >= 0; i--)
if(steps&(1<<i) and x!=-1) x = jmp[i][x];
return x;
}
int lca(int a, int b){
if(a==b) return a;
if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
if(lev[a] < lev[b]) swap(a,b);
a = getPath(a, lev[a]-lev[b]);
for(int i = lgn-1; i >= 0; i--)
if(jmp[i][a]!=-1 and jmp[i][a]!=jmp[i][b])
a = jmp[i][a], b = jmp[i][b];
return jmp[0][a];
}
int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }
void unionSet(Edge &e){
int i = e.u, j = e.v; wei[e.i] = e.w;
int x = findSet(i), y = findSet(j);
p[x]=p[y]=p[num]=num;
if(x!=y) adj[num].pb(y);
adj[num].pb(x); line[num]-=(x==y) | !line[x] | !line[y];
good[num] |= good[x] | good[y] | !line[num];
num++;
}
void dfs(int s, int p){
if(p!=-1) lev[s] = lev[p]+1, jmp[0][s] = p;
for(auto u : adj[s]) if(u!=p) dfs(u,s);
}
void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
n = N, m = M; num = n; memset(jmp,-1,sizeof(jmp));
for(int i = 0; i < n+m; i++) p[i] = i, line[i] = 1;
for(int i = 0; i < m; i++) edge[i] = {u[i],v[i],w[i],i};
sort(edge,edge+M,[&](Edge x, Edge y){ return x.w<y.w; });
for(int i = 0; i < m; i++) edge[i].i=i, unionSet(edge[i]);
dfs(num-1,-1);
for(int i = 1; i < lgn; i++)
for(int j = 0; j+(1<<i)-1 < n; j++)
if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}
int getMinimumFuelCapacity(int x, int y) {
int z = lca(x,y);
while(jmp[0][z]!=-1 and !good[z])
for(int i = lgn-1; i >= 0; i--)
if(jmp[i][z]!=-1 and !good[z]) z = jmp[i][z];
return good[z]?wei[z-n]:-1;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/
