#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll; // warning
namespace{
const ll mxN=2e5+5;
const ll inf=1e18;
const ll LOG=20;
struct edge{
ll u, v, w;
bool operator<(const edge &tar) const{
return w<tar.w;
}
};
ll n, m;
vll adj[mxN];
vector<pll> adj2[mxN];
ll deg[mxN];
bool visited[mxN];
ll dumb[mxN];
ll oth[mxN];
vector<edge> edges;
ll dsu[mxN];
ll p[mxN], d[mxN];
ll up[mxN][LOG];
ll up2[mxN][LOG];
ll find_set(ll tar){
if(dsu[tar]<0) return tar;
return dsu[tar]=find_set(dsu[tar]);
}
void unite(ll a, ll b){
ll f=find_set(a);
ll s=find_set(b);
if(abs(dsu[f])<abs(dsu[s])) swap(f, s);
dsu[f]+=dsu[s];
dsu[s]=f;
}
void dfs(ll cur, ll w){
if(visited[cur]) return;
visited[cur]=1;
dumb[cur]=w;
for(auto &it:adj[cur]){
dfs(it, w);
}
}
void dfs2(ll cur, ll par, ll dep, ll w){
p[cur]=par;
up[cur][0]=par;
up2[cur][0]=w;
d[cur]=dep;
for(auto &[chd, ww]:adj2[cur]){
if(chd==par) continue;
dfs2(chd, cur, dep+1, ww);
}
}
pll kth(ll tar, ll k){
ll re=0;
for(ll i=0;i<LOG;i++){
if(k&(1LL<<i)){
re=max(re, up2[tar][i]);
tar=up[tar][i];
}
}
return {tar, re};
}
pll lca(ll a, ll b){
if(d[a]>d[b]) swap(a, b);
ll re=0;
pll tep=kth(b, d[b]-d[a]);
re=tep.S;
b=tep.F;
if(a==b){
return {a, re};
}
for(ll i=LOG-1;i>=0;i--){
if(up[a][i]!=up[b][i]){
re=max(re, up2[a][i]);
re=max(re, up2[b][i]);
a=up[a][i];
b=up[b][i];
}
}
re=max(re, up2[a][0]);
re=max(re, up2[b][0]);
return {up[a][0], re};
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N;
m=M;
memset(deg, 0, sizeof(deg));
memset(visited, 0, sizeof(visited));
memset(dsu, -1, sizeof(dsu));
for(ll i=0;i<n;i++){
dumb[i]=inf;
}
for(ll i=0;i<m;i++){
edges.pb({U[i], V[i], W[i]});
}
sort(edges.begin(), edges.end());
for(auto &it:edges){
adj[it.u].pb(it.v);
adj[it.v].pb(it.u);
deg[it.u]++;
deg[it.v]++;
if(visited[it.u] || visited[it.v]){
dfs(it.u, it.w);
dfs(it.v, it.w);
}
else{
if(deg[it.u]>2 || deg[it.v]>2){
dfs(it.u, it.w);
dfs(it.v, it.w);
}
else if(deg[it.u]==2 && deg[it.v]==2){
if(oth[it.u]==it.v){
dfs(it.u, it.w);
dfs(it.v, it.w);
}
else{
ll f=oth[it.u];
ll s=oth[it.v];
oth[f]=s;
oth[s]=f;
}
}
else if(deg[it.u]==2){
ll f=oth[it.u];
oth[f]=it.v;
oth[it.v]=f;
}
else if(deg[it.v]==2){
ll f=oth[it.v];
oth[f]=it.u;
oth[it.u]=f;
}
else{
oth[it.u]=it.v;
oth[it.v]=it.u;
}
}
}
for(auto &it:edges){
if(find_set(it.u)!=find_set(it.v)){
adj2[it.u].pb({it.v, it.w});
adj2[it.v].pb({it.u, it.w});
unite(it.u, it.v);
}
}
dfs2(0, 0, 0, 0);
for(ll j=1;j<LOG;j++){
for(ll i=0;i<n;i++){
up[i][j]=up[up[i][j-1]][j-1];
up2[i][j]=max(up2[i][j-1], up2[up[i][j-1]][j-1]);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
ll ans=max(dumb[x], dumb[y]);
ans=max(ans, lca(x, y).S);
if(ans==inf){
return -1;
}
return (int) ans;
}
