#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;
bool good[maxn];
int jmp[lgn][maxn], goodd[lgn][maxn];
vector<int> adj[maxn];
struct Edge{ int u, v, w; };
int p[maxn], lev[maxn], wei[maxn], deg[maxn];
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 lca(a,b);
}
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[num] = e.w;
int x = findSet(i), y = findSet(j);
deg[x]++, deg[y]++;
p[x]=p[y]=p[num]=num;
if(x!=y) adj[num].pb(y);
adj[num].pb(x);
goodd[0][i] = good[num] |= good[x]|good[y]|(deg[x]>=3)|(deg[y]>=3)|(x==y);
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;
for(int i = 0; i < m; i++) edge[i] = {u[i],v[i],w[i]};
sort(edge,edge+m,[&](Edge &x, Edge &y){ return x.w<y.w; });
for(int i = 0; i < m; i++) unionSet(edge[i]);
dfs(num-1,-1);
for(int i = 1; i < lgn; i++)
for(int j = 0; j+(1<<i)-1 < num; j++)
if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
for(int i = 1; i < lgn; i++)
for(int j = 0; j+(1<<i)-1 < num; j++)
goodd[i][j] = goodd[i-1][goodd[i-1][j]];
}
int getMinimumFuelCapacity(int x, int y) {
int z = lca(x,y);
for(int i = lgn-1; i >= 0; i--)
if(jmp[i][z]!=-1 and !goodd[i][z]) z = jmp[i][z];
if(good[z]) return wei[z];
if(jmp[0][z]!=-1) z=jmp[0][z];
return good[z]?wei[z]:-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
*/
