#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#include "swap.h"
namespace dsu
{
int up[100005];
void build(int n)
{
ff(i,0,n) up[i]=-1;
}
int Up(int x)
{
if (up[x]<0) return x;
return up[x]=Up(up[x]);
}
void dsu(int a, int b)
{
a=Up(a),b=Up(b);
if (a==b) return;
if (up[a]<up[b]) swap(a,b);
up[b]+=up[a],up[a]=b;
}
}
//kad nadjemo spanning tree:
vector<vector<pii>> g(100005);
int tin[100005],tout[100005];
int up[17][100005],we[17][100005],twe[17][100005];
int darksoul[100005];
int VREME=0;
void dfs(int p, int q, int qw)
{
tin[p]=++VREME,up[0][p]=q,we[0][p]=qw;
for (auto [it,w] : g[p]) if (it!=q) dfs(it,p,w);
tout[p]=VREME;
}
void build(int n)
{
ff(i,0,n)
{
vector<int> temp;
for (auto [it,w] : g[i]) temp.pb(w);
if ((int)temp.size()<3) twe[0][i]=mod;
else sort(all(temp)),twe[0][i]=temp[2];
}
ff(k,1,17) ff(i,0,n)
{
up[k][i]=up[k-1][up[k-1][i]];
we[k][i]=max(we[k-1][i],we[k-1][up[k-1][i]]);
twe[k][i]=min(twe[k-1][i],twe[k-1][up[k-1][i]]);
}
ff(i,0,n) darksoul[i]=mod;
}
bool anc(int a, int b)
{
return tin[a]<=tin[b] && tout[a]>=tout[b];
}
int Lca(int a, int b, int &maxput, int &mintwe)
{
if (a==b) return a;
if (anc(b,a)) swap(a,b);
if (anc(a,b))
{
maxput=max(maxput,we[0][b]);
b=up[0][b];
if (a==b)
{
mintwe=min(mintwe,darksoul[a]);
return a;
}
bff(k,0,17) if (!anc(up[k][b],a))
{
maxput=max(maxput,we[k][b]);
mintwe=min(mintwe,twe[k][b]);
b=up[k][b];
}
maxput=max(maxput,we[0][b]);
mintwe=min(mintwe,twe[0][b]);
mintwe=min(mintwe,darksoul[a]);
return a;
}
maxput=max(maxput,we[0][a]);
maxput=max(maxput,we[0][b]);
a=up[0][a],b=up[0][b];
if (a==b)
{
mintwe=min(mintwe,twe[0][a]);
mintwe=min(mintwe,darksoul[a]);
return a;
}
bff(k,0,17) if (!anc(up[k][a],b))
{
maxput=max(maxput,we[k][a]);
mintwe=min(mintwe,twe[k][a]);
a=up[k][a];
}
bff(k,0,17) if (!anc(up[k][b],a))
{
maxput=max(maxput,we[k][b]);
mintwe=min(mintwe,twe[k][b]);
b=up[k][b];
}
maxput=max(maxput,we[0][a]);
maxput=max(maxput,we[0][b]);
mintwe=min(mintwe,twe[0][a]);
mintwe=min(mintwe,twe[0][b]);
a=up[0][a];
mintwe=min(mintwe,twe[0][a]);
mintwe=min(mintwe,darksoul[a]);
return a;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
vector<pair<int,pii>> sorta;
ff(i,0,m) sorta.pb({w[i],{u[i],v[i]}});
sort(all(sorta));
vector<pair<int,pii>> izdajnici;
dsu::build(n);
for (auto it : sorta)
{
int a=it.yy.xx,b=it.yy.yy;
int pa=dsu::Up(a),pb=dsu::Up(b);
if (pa!=pb) g[a].pb({b,it.xx}),g[b].pb({a,it.xx}),dsu::dsu(pa,pb);
else izdajnici.pb(it);
}
dfs(0,0,0);
build(n);
for (auto it : izdajnici)
{
int nebitno=-1;
int a=it.yy.xx,b=it.yy.yy,w=it.xx;
int c=Lca(a,b,nebitno,nebitno);
darksoul[c]=min(darksoul[c],w);
}
}
int getMinimumFuelCapacity(int a, int b)
{
int maxput=0,spas=mod;
int c=Lca(a,b,maxput,spas);
if (spas==mod) return -1;
return max(maxput,spas);
}
/*
5 4
0 1 1
1 2 1
2 3 1
3 4 1
10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
11 10
0 1 5
1 2 4
2 3 3
2 4 10
1 5 1
5 6 2
5 7 2
0 8 10
8 9 1
8 10 1
10
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
*/
