/*input
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/
#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;
vector<pii> g[maxn];
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]}});
g[U[i]].pb({V[i],W[i]});
g[V[i]].pb({U[i],W[i]});
}
sort(ALL(ed));
}
int par[maxn];
pair<bool,pii> cmp[maxn];
int find(int u){
if(par[u]==u) return u;
return par[u]=find(par[u]);
}
vector<int> v[maxn];
void merge(int a,int b){
int oa=a,ob=b;
a=find(a),b=find(b);
if(a==b){
cmp[a].f=0;
return;
}
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 cmp[a].f=0;
}
else cmp[a].f=0;
}
const int INF=0x3f3f3f3f;
int getMinimumFuelCapacity(int x, int y) {
REP(i,n) par[i]=i,v[i].clear(),cmp[i]={1,{i,i}};
int ans=-1;
for(auto a:ed){
merge(a.s.f,a.s.s);
if(find(x)==find(y)){
if(!cmp[find(x)].f){
return a.f;
}
}
}
return -1;
}
