#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e5+5;
const int lg = 19;
int n,par[N],h[N],st[N][lg],cur,ck[N],val[N],deg[N];
vector<int>adj[N];
int find(int u){
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void join(int u, int v, int w){
int x = u;
int y = v;
u = find(u);
v = find(v);
deg[x]++;
deg[y]++;
par[u] = par[v] = par[cur] = cur;
adj[cur].push_back(u);
val[cur] = w;
if(u != v) adj[cur].push_back(v);
if(u == v || ck[u] || ck[v] || deg[x] >= 3 || deg[y] >= 3) ck[cur] = 1;
cur++;
}
void dfs(int u, int p){
st[u][0] = p;
h[u] = h[p]+1;
for(int i = 1; i < lg; i++) st[u][i] = st[st[u][i-1]][i-1];
for(int v: adj[u]) dfs(v,u);
}
int lca(int u, int v){
if(h[u] < h[v]) swap(u,v);
for(int i = lg-1; i >= 0; i--){
if(h[st[u][i]] >= h[v]) u = st[u][i];
}
if(u == v) return u;
for(int i = lg-1; i >= 0; i--){
if(st[u][i] != st[v][i]){
u = st[u][i];
v = st[v][i];
}
}
return st[u][0];
}
struct edges{
int u,v,w;
};
bool cmp(edges a, edges b){
return a.w < b.w;
}
vector<edges>loj;
void init(int n, int m, vector<int>u, vector<int>v, vector<int>w){
for(int i = 0; i < m; i++){
u[i]++;
v[i]++;
loj.push_back({u[i],v[i],w[i]});
}
sort(loj.begin(),loj.end(),cmp);
for(int i = 1; i <= n; i++) par[i] = i;
cur = n+1;
for(auto[u,v,w]: loj) join(u,v,w);
dfs(n+m,0);
}
int getMinimumFuelCapacity(int u, int v){
u++;
v++;
int dm = lca(u,v);
if(ck[dm]) return val[dm];
for(int i = lg-1; i >= 0; i--){
if(st[dm][i] != 0 && !ck[st[dm][i]]) dm = st[dm][i];
}
if(st[dm][0] == 0) return -1;
else return val[st[dm][0]];
}
