//chockolateman
#include<bits/stdc++.h>
using namespace std;
int n,m,min_good[500005],s[500005],p[500005],deg[500005],Nodes,up[500005][20],up_max[500005][20],tin[500005],tout[500005],timer;
stack<int> cur_elem[500005];
bool is_good[500005];
vector<pair<int,int>> adj[500005];
int find_Sett(int i)
{
if(p[i]==i)
return p[i];
p[i] = find_Sett(p[i]);
return p[i];
}
bool is_Same_Sett(int i,int j)
{
return find_Sett(i)==find_Sett(j);
}
void union_Sett(int i,int j,int w)
{
int x = find_Sett(i);
int y = find_Sett(j);
deg[i]++;
deg[j]++;
if(deg[i] > 2)
is_good[x] = true;
if(deg[j] > 2)
is_good[y] = true;
if(is_Same_Sett(i,j))
is_good[x] = true;
else
{
if(s[x] < s[y])
swap(x,y);
p[y] = x;
s[x] += s[y];
is_good[x] |= is_good[y];
if(cur_elem[y].size() > cur_elem[x].size())
swap(cur_elem[x],cur_elem[y]);
while(!cur_elem[y].empty())
{
int k = cur_elem[y].top();
cur_elem[y].pop();
cur_elem[x].push(k);
}
Nodes++;
adj[x].push_back({Nodes,w});
adj[y].push_back({Nodes,w});
adj[Nodes].push_back({x,w});
adj[Nodes].push_back({y,w});
p[x] = Nodes;
p[y] = Nodes;
p[Nodes] = Nodes;
s[Nodes] = s[x];
swap(cur_elem[Nodes],cur_elem[x]);
}
if(is_good[x])
{
while(!cur_elem[x].empty())
{
int k = cur_elem[x].top();
cur_elem[x].pop();
min_good[k] = w;
}
}
}
pair<int,pair<int,int>> edges[200005];
void dfs(int v,int par,int par_w)
{
tin[v] = ++timer;
up[v][0] = par;
up_max[v][0] = par_w;
for(int L = 1 ; L <= 18 ; L++)
{
up[v][L] = up[up[v][L-1]][L-1];
up_max[v][L] = max(up_max[v][L-1],up_max[up[v][L-1]][L-1]);
}
for(auto e : adj[v])
{
int u = e.first;
int w = e.second;
if(u != par)
dfs(u,v,w);
}
tout[v] = ++timer;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
Nodes = N;
for(int i = 1 ; i <= N ; i++)
{
p[i] = i;
s[i] = 1;
min_good[i] = -1;
cur_elem[i].push(i);
}
for(int i = 1 ; i <= M ; i++)
edges[i] = {W[i-1],{V[i-1]+1,U[i-1]+1}};
sort(edges+1,edges+M+1);
for(int v,u,w,i = 1 ; i <= M ; i++)
{
v = edges[i].second.first;
u = edges[i].second.second;
w = edges[i].first;
union_Sett(v,u,w);
}
dfs(Nodes,Nodes,0);
}
int getMinimumFuelCapacity(int X, int Y) {
X++;
Y++;
int ret = min_good[X];
if(ret==-1)
return -1;
for(int i = 1 ; i <= n ; i++)
{
p[i] = i;
s[i] = 1;
}
sort(edges+1,edges+m+1);
for(int v,u,w,i = 1 ; i <= m ; i++)
{
v = edges[i].second.first;
u = edges[i].second.second;
w = edges[i].first;
union_Sett(v,u,w);
ret = max(ret,w);
if(is_Same_Sett(X,Y))
break;
}
return ret;
}
