//chockolateman
#include<bits/stdc++.h>
using namespace std;
int n,m,min_good[100005],s[100005],p[100005],deg[100005];
stack<int> cur_elem[100005];
bool is_good[100005];
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);
}
}
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];
vector<pair<int,int>> adj[200005];
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
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;
adj[v].push_back({u,w});
adj[u].push_back({u,v});
union_Sett(v,u,w);
}
}
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;
}
