#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];
int dp[100005]; //min twe u subtree
int VREME=0;
int propagate[17][100005];
vector<vector<pii>> uopste(100005);
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] : uopste[i]) temp.pb(w);
if ((int)temp.size()<3) dp[i]=mod;
else sort(all(temp)),dp[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]]);
}
}
bool anc(int a, int b)
{
return tin[a]<=tin[b] && tout[a]>=tout[b];
}
int Lca(int a, int b, int &maxput)
{
bff(k,0,17) if (!anc(up[k][a],b))
{
maxput=max(maxput,we[k][a]);
a=up[k][a];
}
bff(k,0,17) if (!anc(up[k][b],a))
{
maxput=max(maxput,we[k][b]);
b=up[k][b];
}
if (anc(b,a)) swap(a,b);
if (anc(a,b))
{
maxput=max(maxput,we[0][b]);
return a;
}
maxput=max(maxput,we[0][a]);
maxput=max(maxput,we[0][b]);
a=up[0][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) uopste[u[i]].pb({v[i],w[i]}),uopste[v[i]].pb({u[i],w[i]});
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);
}
ff(i,0,n) dp[i]=mod;
dfs(0,0,0);
build(n);
ff(k,0,17) ff(i,0,n) propagate[k][i]=mod;
for (auto it : izdajnici)
{
int a=it.yy.xx,b=it.yy.yy,w=it.xx;
bff(k,0,17) if (!anc(up[k][a],b))
{
propagate[k][a]=min(propagate[k][a],w);
a=up[k][a];
}
bff(k,0,17) if (!anc(up[k][b],a))
{
propagate[k][b]=min(propagate[k][b],w);
b=up[k][b];
}
if (anc(b,a)) swap(a,b);
if (anc(a,b))
{
propagate[0][b]=min(propagate[0][b],w);
}
else
{
propagate[0][b]=min(propagate[0][b],w);
propagate[0][a]=min(propagate[0][a],w);
}
}
bff(k,0,16) ff(i,0,n)
{
propagate[k][i]=min(propagate[k][i],propagate[k+1][i]);
propagate[k][up[k][i]]=min(propagate[k][up[k][i]],propagate[k+1][i]);
}
ff(i,0,n) dp[i]=min(dp[i],propagate[0][i]);
vector<bool> vis(n,false);
priority_queue<pii,vector<pii>,greater<pii>> pq;
ff(i,0,n) pq.push({dp[i],i});
while (!pq.empty())
{
auto [d,p]=pq.top();
pq.pop();
if (vis[p]) continue;
vis[p]=true;
dp[p]=d;
for (auto [it,w] : uopste[p]) pq.push({max(d,w),it});
}
}
int getMinimumFuelCapacity(int a, int b)
{
int maxput=0;
int c=Lca(a,b,maxput);
if (dp[c]==mod) return -1;
return max(maxput,dp[c]);
}
/*
4 4
0 1 1
1 2 2
2 3 3
3 0 4
4
0 1
1 2
2 3
3 0
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
1 0
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
*/
