// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
struct ufds_rollback {
vector<vii>p;
vi rank,max_deg,possible,deg;
vector<bool>cycle;
ufds_rollback(int n) {
deg.assign(n,0);
rank.assign(n,0);
cycle.assign(n,0);
max_deg.assign(n,0);
possible.assign(n,INF);
p.resize(n);
rep(i,0,n)p[i].emplace_back(0,i);
}
int find(int i,const int &mx) {
auto it=upper_bound(all(p[i]),ii(mx,INF));
--it;
//cout<<"i = "<<i<<" mx = "<<mx<<" val = "<<it->first<<" p = "<<it->second<<endl;
if(it->second==i)return i;
else return find(it->second,mx);
return 0;
}
void union_set(int i,int j,int val) {
int u=find(i,val);
int v=find(j,val);
if(u==v) {
cycle[u]=1;
possible[u]=min(possible[u],val);
return;
}
++deg[i];
++deg[j];
max_deg[u]=max(max_deg[u],deg[i]);
max_deg[v]=max(max_deg[v],deg[j]);
if(rank[u]<rank[v])swap(u,v);
if(rank[u]==rank[v])++rank[u];
if(p[v].back().first==val)p[v].pop_back();
p[v].emplace_back(val,u);
max_deg[u]=max(max_deg[u],max_deg[v]);
if(possible[v]!=INF||max_deg[u]>=3) possible[u]=min(possible[u],val);
}
};
ufds_rollback ufds(100001);
vector<iii> edges;
int n,m;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
m=M;
rep(i,0,m) edges.pb({W[i],{U[i],V[i]}});
sort(all(edges));
//rep(i,0,n) {
// auto it=ufds.p[i].begin();
// cout<<sz(ufds.p[i])<<' '<<it->first<<' '<<it->second<<' ';
// ufds.find(i,0);
//}
trav(edge,edges) {
int u,v,w;
w=edge.first;
tie(u,v)=edge.second;
ufds.union_set(u,v,w);
//cout<<"u = "<<u<<" v = "<<v<<" w = "<<w<<endl;
}
edges.pb({-1,{0,0}});
}
int getMinimumFuelCapacity(int X, int Y) {
int u=X,v=Y;
int lo=0,hi=m;
while(lo!=hi) {
int mid=(lo+hi)/2;
int w=edges[mid].first;
int p=ufds.find(u,w);
if(p==ufds.find(v,w)&&ufds.possible[p]<=w) hi=mid;
else lo=mid+1;
}
return edges[lo].first;
}
/*
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::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) {
printf("%d\n", minimum_fuel_capacities[i]);
}
return 0;
}*/
