#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 4e5+10;
vector<int> v;
int N,M;
vector<pair<int,pii>> edges;
vector<int> tree[mxn];
int dp[mxn][20];
int par[mxn][20];
pii val[mxn];
int dep[mxn];
int rt;
namespace INIT{
int deg[mxn];
struct DSU{
bool chn[mxn];
int cnt[mxn][2];
int head[mxn];
int sz[mxn],dsu[mxn];
void init(int n){
for(int i = 0;i<=n;i++){
dsu[i] = i,sz[i] = 1;
chn[i] = true;
cnt[i][0] = 1;
head[i] = i;
}
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void upd(int now){
int r = root(now);
if(deg[now]<2){
cnt[r][deg[now]]--;
deg[now]++;
if(deg[now]<2)cnt[r][deg[now]]++;
}
else{
chn[r] = false;
}
return;
}
void check(int r){
r = root(r);
if(cnt[r][1]>2)chn[r] = false;
return;
}
void onion(int a,int b){
int ra = root(a),rb = root(b);
if(ra == rb){
chn[ra] = false;
return;
}
if(sz[ra]<sz[rb]){
swap(a,b);
swap(ra,rb);
}
if(!chn[ra]||!chn[rb])chn[ra] = false;
sz[ra] += sz[rb];
dsu[rb] = ra;
for(int i = 0;i<2;i++)cnt[ra][i] += cnt[rb][i];
upd(a);
upd(b);
check(ra);
return;
}
};
DSU dsu;
void dfs(int now){
dp[now][0] = val[now].sc;
for(int i = 1;i<20;i++){
par[now][i] = par[par[now][i-1]][i-1];
dp[now][i] = dp[par[now][i-1]][i-1];
}
for(auto nxt:tree[now]){
//cout<<now<<","<<nxt<<endl;
dep[nxt] = dep[now]+1;
par[nxt][0] = now;
dfs(nxt);
}
return;
}
void GO(){
dsu.init(N-1);
for(int i = N;i<mxn;i++)dsu.dsu[i] = i,dsu.sz[i] = 1;
for(int i = 0;i<N;i++)val[i].sc = 1;
int pt = N-1;
for(int i = 0;i<edges.size();i++){
auto [a,b] = edges[i].sc;
int ra = dsu.root(a),rb = dsu.root(b);
int w = edges[i].fs;
pt++;
val[pt].fs = w;
tree[pt].push_back(dsu.head[ra]);
if(ra != rb)tree[pt].push_back(dsu.head[rb]);
dsu.onion(a,b);
dsu.head[dsu.root(a)] = pt;
//cout<<pt<<' '<<dsu.root(a)<<':'<<dsu.chn[dsu.root(a)]<<endl;
val[pt].sc = dsu.chn[dsu.root(a)];
}
rt = pt;
par[rt][0] = rt;
//for(int i = 0;i<=rt;i++)cout<<i<<":"<<val[i].sc<<endl;
dfs(rt);
return;
}
}
void init(int NN, int MM,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N = NN,M = MM;
for(int i = 0;i<M;i++){
edges.push_back(make_pair(W[i],pii(U[i],V[i])));
}
sort(edges.begin(),edges.end());
INIT::GO();
}
int getans(int s,int t){
if(dep[s]<dep[t])swap(s,t);
int d = dep[s]-dep[t];
for(int i = 19;i>=0;i--){
if(d&(1<<i))s = par[s][i];
}
for(int i = 19;i>=0;i--){
if(par[s][i] != par[t][i])s = par[s][i],t = par[t][i];
}
if(s != t)s = t = par[s][0];
for(int i = 19;i>=0;i--){
if(dp[s][i])s = par[s][i];
}
if(val[s].sc)s = par[s][0];
if(val[s].sc)return -1;
else return val[s].fs;
}
int getMinimumFuelCapacity(int s, int t) {
return getans(s,t);
}
