#include "swap.h"
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
vector<pair<int,pair<int,int> > >edges;
bool cmp(pair<int,pair<int,int> >a,pair<int,pair<int,int> >b)
{
return a.first<b.first;
}
vector<pair<long long,long long> >adj[200005];
long long backedge[200005];
long long rasp[200005];
long long jos[200005];
long long sus[200005];
long long lvl[200005];
vector<long long>vec;
long long inf=1e14;
void dfs(int curr,int parent)
{
int i,k;
lvl[curr]=lvl[parent]+1;
vec.clear();
jos[curr]=inf;
if(adj[curr].size()>=3)
{
for(i=0; i<adj[curr].size(); i++)
{
vec.push_back(adj[curr][i].second);
}
sort(vec.begin(),vec.end());
jos[curr]=vec[2];
}
if(backedge[curr]!=0)
{
jos[curr]=min(jos[curr],backedge[curr]);
}
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=parent)
{
dfs(k,curr);
}
jos[curr]=min(jos[curr],max(jos[k],adj[curr][i].second));
}
}
void dfs2(int curr,int par,long long val)
{
long long i,k;
sus[curr]=max(min(jos[par],sus[par]),val);
rasp[curr]=min(sus[curr],jos[curr]);
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=par)
{
dfs2(k,curr,adj[curr][i].second);
}
}
}
///bl e parinte
/// drum e cost de a merge la parinte
/// ext e cost minim degreee 3
long long bl[33][200005];
long long ext[33][200005];
long long drum[33][200005];
int sef[200005];
void dfs3(int curr,int par,long long val)
{
long long i,k;
bl[0][curr]=par;
ext[0][curr]=min(rasp[par],rasp[curr]);
drum[0][curr]=val;
for(i=1; i<=30; i++)
{
bl[i][curr]=bl[i-1][bl[i-1][curr]];
ext[i][curr]=min(ext[i-1][curr],ext[i-1][bl[i-1][curr]]);
drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]);
}
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=par)
{
dfs3(k,curr,adj[curr][i].second);
}
}
}
int lca (long long a,long long b)
{
long long i,curr;
if(lvl[a]<lvl[b])
{
swap(a,b);
}
for(i=30; i>=0; i--)
{
curr=bl[i][a];
if(lvl[curr]>=lvl[b])
{
a=curr;
}
}
if(a==b)
{
return a;
}
else
{
for(i=30; i>=0; i--)
{
if(bl[i][a]!=bl[i][b])
{
a=bl[i][a];
b=bl[i][b];
}
}
return bl[0][a];
}
}
pair<long long,long long> calc (int a,int b)
{
long long curr,maxdrum=0,minrel=inf,i;
if(a==b)
{
return make_pair(0,rasp[a]);
}
minrel=min(rasp[a],rasp[b]);
maxdrum=drum[0][a];
for(i=30; i>=0; i--)
{
curr=bl[i][a];
if(lvl[curr]>=lvl[b])
{
maxdrum=max(maxdrum,drum[i][a]);
minrel=min(minrel,ext[i][a]);
a=curr;
}
}
return make_pair(maxdrum,minrel);
}
int find (int u)
{
if(sef[u]==u)
{
return u;
}
return sef[u]=find(sef[u]);
}
int merge (int a,int b)
{
a=find(a);
b=find(b);
if(a!=b)
{
sef[a]=b;
return 1;
}
return 0;
}
void init(int n, int m,vector<int> a, vector<int> b, vector<int> w)
{
int i,x,y;
long long val;
for(i=1;i<=n;i++)
{
sef[i]=i;
}
for(i=1; i<=m; i++)
{
a[i-1]++;
b[i-1]++;
edges.push_back({w[i-1],{a[i-1],b[i-1]}});
}
sort(edges.begin(),edges.end(),cmp);
for(i=0; i<m; i++)
{
val=edges[i].first;
x=edges[i].second.first;
y=edges[i].second.second;
if(merge(x,y)==1)
{
adj[x].push_back({y,val});
adj[y].push_back({x,val});
}
else
{
if(backedge[x]==0)
{
backedge[x]=val;
}
else
{
backedge[x]=min(backedge[x],val);
}
if(backedge[y]==0)
{
backedge[y]=val;
}
else
{
backedge[y]=min(backedge[y],val);
}
}
}
sus[0]=inf;
jos[0]=inf;
dfs(1,0);
dfs2(1,0,0);
dfs3(1,0,0);
}
int getMinimumFuelCapacity(int x, int y)
{
long long lc;
x++;
y++;
pair<long long,long long>a;
pair<long long,long long>b;
lc=lca(x,y);
a=calc(x,lc);
b=calc(y,lc);
a.first=max(a.first,b.first);
a.second=min(a.second,b.second);
a.first=max(a.first,a.second);
if(a.first==inf)
{
return -1;
}
else
{
return a.first;
}
}
/*int main()
{
int N, M;
cin>>N>>M;
vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i)
{
cin>>U[i]>>V[i]>>W[i];
}
int Q;
cin>>Q;
vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i)
{
cin>>X[i]>>Y[i];
}
init(N, M, U, V, W);
vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i)
{
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i)
{
cout<<minimum_fuel_capacities[i]<<'\n';
}
return 0;
}*/
