/*input
3 2
0 1 5
0 2 5
1
1 2
*/
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
#define MXTO(a,b) a=max(a,b)
#define MNTO(a,b) a=min(a,b)
#define sz(x) (int)x.size()
#define pb push_back
const int maxn=1e5+5;
vector<pair<int,pii>> ed;
int n,m;
int par[maxn];
pair<bool,pii> cmp[maxn];
vector<int> vv[maxn];
int find(int u){
if(par[u]==u) return u;
return par[u]=find(par[u]);
}
vector<pii> sp[maxn];
int sc[maxn];
const int INF=0x3f3f3f3f;
void merge(int t,int a,int b){
int oa=a,ob=b;
a=find(a),b=find(b);
if(a==b){
if(sc[a]==INF) sc[a]=t;
cmp[a].f=0;
return;
}
if(sz(vv[a])<sz(vv[b])) swap(a,b),swap(oa,ob);
par[b]=a;
if(cmp[a].f and cmp[b].f){
if((oa==cmp[a].s.f or oa==cmp[a].s.s) and (ob==cmp[b].s.f or ob==cmp[b].s.s)){
cmp[a].f=1;
if(oa==cmp[a].s.f) cmp[a].s.f=cmp[a].s.s;
if(ob==cmp[b].s.f) cmp[a].s.s=cmp[b].s.s;
else cmp[a].s.s=cmp[b].s.f;
}
else{
if(sc[a]==INF) sc[a]=t;
cmp[a].f=0;
}
}
else{
if(sc[a]==INF) sc[a]=t;
cmp[a].f=0;
}
for(int x:vv[b]) sp[x].pb({t,a}),vv[a].pb(x);
vv[b].clear();
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N,m=M;
REP(i,M){
ed.pb({W[i],{U[i],V[i]}});
}
sort(ALL(ed));
REP(i,n) par[i]=i,cmp[i]={1,{i,i}},vv[i].pb(i),sc[i]=INF,sp[i].pb({-1,i});
REP(i,m){
auto a=ed[i];
merge(i,a.s.f,a.s.s);
}
}
int gp(int x,int t){
return (*prev(upper_bound(ALL(sp[x]),make_pair(t,INF)))).s;
}
int getMinimumFuelCapacity(int x, int y) {
int l=0,r=m-1;
int a=gp(x,m-1),b=gp(y,m-1);
if(a!=b or sc[a]==INF){
return -1;
}
while(l<r){
int mid=(l+r)/2;
int a=gp(x,mid),b=gp(y,mid);
if(a==b and sc[a]<=mid) r=mid;
else l=mid+1;
}
return ed[l].f;
}
