#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1100000000
#define sz(x) (int)(x).size()
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ii pair<int,int>
int n,m;
vector<pair<int,ii> > edges;
int p[100005];
int deg[100005];
int maxdeg[100005],deg1[100005];
void init_uf() {
for (int i=0;i<n;i++) {
p[i]=i;
deg[i]=maxdeg[i]=deg1[i]=0;
}
}
int find(int x) {
return (p[x]==x)?x:(p[x]=find(p[x]));
}
void join(int x,int y) {
int a=find(x),b=find(y);
if (a!=b) {
maxdeg[b]=max(maxdeg[b],maxdeg[a]);
deg1[b]+=deg1[a];
p[a]=b;
}
}
bool same(int x,int y) {
return (find(x)==find(y));
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N;
m=M;
for (int i=0;i<m;i++) {
edges.pb(mp(W[i],mp(U[i],V[i])));
}
sort(all(edges));
}
int getMinimumFuelCapacity(int x, int y) {
init_uf();
for (auto e:edges) {
int w=e.first;
int a=e.second.first;
int b=e.second.second;
if (deg[a]==0) deg1[find(a)]++;
if (deg[a]==1) deg1[find(a)]--;
deg[a]++;
maxdeg[find(a)]=max(maxdeg[find(a)],deg[a]);
if (deg[b]==0) deg1[find(b)]++;
if (deg[b]==1) deg1[find(b)]--;
deg[b]++;
maxdeg[find(b)]=max(maxdeg[find(b)],deg[b]);
if (!same(a,b)) join(a,b);
if (same(x,y)) {
int v=find(x);
if (maxdeg[v]>2) return w;
if (maxdeg[v]==2 && deg1[v]==0) return w;
}
}
return -1;
}
