#include "swap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const int inf=1e9;
const int mxn=1e5+5;
vector<int> U,V,W;
vector<int> mn(mxn,inf);
vector<vector<pair<int,int>>> adj(mxn);
vector<vector<int>> up(mxn,vector<int>(20));
vector<vector<int>> mx(mxn,vector<int>(20));
vector<vector<int>> upmn(mxn,vector<int>(20));
vector<multiset<int>> ch(mxn);
vector<int> pid(mxn,-1);
vector<int> d(mxn);
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
return true;
}
};
int go(int x,int len){
for(int i=0;i<20;i++){
if(len&(1<<i)){
x=up[x][i];
}
}
return x;
}
pair<int,int> lca(int a,int b){
if(d[a]<d[b]) swap(a,b);
int len=d[a]-d[b];
int ans=0;
for(int i=0;i<20;i++){
if(len&(1<<i)){
ans=max(ans,mx[a][i]);
a=up[a][i];
}
}
if(a==b) return make_pair(a,ans);
for(int i=19;i>=0;i--){
int ta=up[a][i];
int tb=up[b][i];
if(ta!=tb){
ans=max(ans,mx[a][i]);
ans=max(ans,mx[b][i]);
a=tb;
b=tb;
}
}
ans=max({ans,mx[a][0],mx[b][0]});
return make_pair(up[a][0],ans);
}
int path(int a,int b){
if(a==b) return inf;
int x=a;
int ans=inf;
for(int i=19;i>=0;i--){
int y=up[x][i];
if(d[y]>d[b]){
ans=min(ans,upmn[x][i]);
x=up[x][i];
}
}
//cout<<a<<' '<<b<<' '<<ans<<'\n';
return ans;
}
int val(int a){
int ans=mn[a];
for(auto v:adj[a]){
if(v.f==up[a][0]) continue;
ans=min(ans,W[v.s]);
}
return ans;
}
}
void init(int n, int m,
std::vector<int> u, std::vector<int> v, std::vector<int> w) {
U=u;
V=v;
W=w;
W.push_back(inf);
vector<pair<int,int>> e(m);
for(int i=0;i<m;i++){
e[i]={W[i],i};
}
sort(all(e));
vector<bool> tree(m);
DSU dsu(n);
for(int i=0;i<m;i++){
int id=e[i].s;
if(dsu.unite(U[id],V[id])){
tree[id]=true;
//cout<<U[id]<<' '<<V[id]<<'\n';
}
}
for(int i=0;i<m;i++){
U[i]++;
V[i]++;
}
for(int i=0;i<m;i++){
if(!tree[i]){
mn[U[i]]=min(mn[U[i]],W[i]);
mn[V[i]]=min(mn[V[i]],W[i]);
continue;
}
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
for(int i=0;i<=n;i++){
ch[i].insert(inf);
}
function<void(int,int)> dfs=[&](int v,int p){
for(auto u:adj[v]){
if(u.f==p) continue;
d[u.f]=d[v]+1;
ch[v].insert(W[u.s]);
dfs(u.f,v);
up[u.f][0]=v;
pid[u.f]=u.s;
mx[u.f][0]=W[u.s];
}
};
pid[1]=m;
dfs(1,0);
upmn[1][0]=inf;
for(int i=2;i<=n;i++){
ch[up[i][0]].erase(ch[up[i][0]].find(W[pid[i]]));
upmn[i][0]=min(mn[up[i][0]],*ch[up[i][0]].begin());
ch[up[i][0]].insert(W[pid[i]]);
}
for(int j=1;j<20;j++){
for(int i=1;i<=n;i++){
up[i][j]=up[up[i][j-1]][j-1];
mx[i][j]=max(mx[i][j-1],mx[up[i][j-1]][j-1]);
upmn[i][j]=min(upmn[i][j-1],upmn[up[i][j-1]][j-1]);
}
}
}
int getMinimumFuelCapacity(int a, int b) {
a++;
b++;
if(d[a]<d[b]) swap(a,b);
pair<int,int> p=lca(a,b);
int c=p.f;
int val=p.s;
int ans=inf;
if(c==b){
ans=min(ans,path(a,b));
//ans=min(ans,val(a));
if(pid[b]!=-1){
//ans=min(ans,W[pid[b]]);
}
}
else{
int A=go(a,d[a]-d[c]-1);
int B=go(b,d[b]-d[c]-1);
ans=min(ans,path(a,c));
ans=min(ans,path(b,c));
//ans=min(ans,val(a));
//ans=min(ans,val(b));
ch[c].erase(ch[c].find(W[pid[A]]));
ch[c].erase(ch[c].find(W[pid[B]]));
ans=min(ans,*ch[c].begin());
ch[c].insert(W[pid[A]]);
ch[c].insert(W[pid[B]]);
ans=min(ans,W[pid[c]]);
}
return (ans==inf?-1:max(ans,val));
}
