#include<bits/stdc++.h>
#include"swap.h"
using namespace std;
#define N 100100
#define J 18
#define inf 0x3f3f3f3f
vector<pair<int,int>>adj[N];
int parent[N],fae[N];
pair<int,int>jump[N][J];
int tin[N],tout[N],t;
void dfs(int u,int fa){
tin[u]=++t;
jump[u][0]={parent[u],fae[u]};
for(int a=1;a<J;++a){
jump[u][a]={jump[jump[u][a-1].first][a-1].first,max({jump[u][a-1].second,jump[jump[u][a-1].first][a-1].second})};
}
for(auto a:adj[u]){
if(a.first==fa)continue;
fae[a.first]=a.second;
parent[a.first]=u;
dfs(a.first,u);
}
tout[u]=t;
}
bool isanc(int u,int v){
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
int get(int u,int v){
int ret=0;
for(int a=J-1;a>=0;--a){
if(!isanc(jump[u][a].first,v)){
ret=max(ret,jump[u][a].second);
u=jump[u][a].first;
}
}
for(int a=J-1;a>=0;--a){
if(!isanc(jump[v][a].first,u)){
ret=max(ret,jump[v][a].second);
v=jump[v][a].first;
}
}
if(u==v)return ret;
if(parent[u]==v)return max(ret,fae[u]);
if(parent[v]==u)return max(ret,fae[v]);
return max({ret,fae[u],fae[v]});
}
int deg[N],kt[N];
int ktv=0;
int getMinimumFuelCapacity(int u,int v){
int ret=max(get(u,v),min(kt[u],kt[v]));
return ret==inf?-1:max(ret,0);
}
struct DSU{
bool mark[N];
int fa[N];
vector<int>buk[N];
int root(int u){return fa[u]==u?u:fa[u]=root(fa[u]);}
void activate(int u){
u=root(u);
if(mark[u])return;
mark[u]=true;
for(auto a:buk[u])kt[a]=ktv;
}
bool merge(int u,int v){
u=root(u),v=root(v);
if(u==v){
activate(u);
return false;
}
if(mark[u])activate(v);
if(mark[v])activate(u);
mark[u]|=mark[v];
if(buk[u].size()<buk[v].size())buk[u].swap(buk[v]);
for(auto a:buk[v])buk[u].push_back(a);
buk[v].clear();
fa[v]=u;
return true;
}
void init(){
for(int a=0;a<N;++a){
fa[a]=a;
buk[a].push_back(a);
}
}
}calc;
void init(int n,int m,vector<int>U,vector<int>V,vector<int>W){
memset(kt,0x3f,sizeof(kt));
calc.init();
vector<int>ord;
for(int a=0;a<m;++a)ord.push_back(a);
sort(ord.begin(),ord.end(),[&](const int&x,const int&y)->bool{return W[x]<W[y];});
for(int i=0;i<m;++i){int a=ord[i];
ktv=W[a];
if((++deg[U[a]])>=3)calc.activate(U[a]);
if((++deg[V[a]])>=3)calc.activate(V[a]);
if(calc.merge(U[a],V[a])){
adj[U[a]].push_back({V[a],W[a]});
adj[V[a]].push_back({U[a],W[a]});
}
}
dfs(0,0);
}
