#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
const int nn = 100005;
int n,m;
struct edge{
int w,u,v;
};
bool cmp(edge a, edge b){
return a.w < b.w;
}
edge edges[200005];
int p[nn], sz[nn], par[nn], mergeweight[nn], lineweight[nn], s[nn], e[nn];
int fs(int x){
if(p[x] == x) return x;
else return p[x] = fs(p[x]);
}
void merge(int a, int b, int w){
int ga = fs(a), gb = fs(b);
if(ga == gb){
if(lineweight[ga] == -1) lineweight[ga] = w;
return;
}
//merge b into a
if(sz[ga] < sz[gb]){
swap(ga,gb);
swap(a,b);
}
par[gb] = ga;
p[gb] = ga;
sz[ga] += sz[gb];
mergeweight[gb] = w;
if(lineweight[gb] != -1 and lineweight[ga] == -1){ //b is not a line, a is -> merge non line to line
lineweight[ga] = w;
}
if(lineweight[ga] == -1 and lineweight[gb] == -1){ //both are lines
int s1 = s[ga], s2 = s[gb], e1 = e[ga], e2 = e[gb];
if(a == s1 and b == s2) s[ga] = e1, e[ga] = e2;
else if (a == s1 and b == e2) s[ga] = s2, e[ga] = e1;
else if (a == e1 and b == s2) s[ga] = s1, e[ga] = e2;
else if (a == e1 and b == e2) s[ga] = s1, e[ga] = s2;
else {
lineweight[ga] = w;
}
}
}
void init(signed N, signed M,
std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
for(int i=0; i<nn; i++) p[i] = i, par[i] = -1, sz[i] = 1, lineweight[i] = -1, mergeweight[i] = -1, s[i] = i, e[i] = i;
n = N, m = M;
for(int i=0; i<m; i++){
int u = U[i], v = V[i], w = W[i];
edges[i] = {w,u,v};
}
sort(edges,edges+m,cmp);
for(int i=0; i<m; i++){
auto[w,u,v] = edges[i];
merge(u,v,w);
}
}
signed getMinimumFuelCapacity(signed X, signed Y) {
int low = 0, high = 1e9+1;
while(high-low > 1){
int mid = (high+low)/2;
int x = X, y = Y;
//dd(mid)
while(mergeweight[x] <= mid){
if(par[x] == -1) break;
x = par[x];
}
while(mergeweight[y] <= mid){
if(par[y] == -1) break;
y = par[y];
}
if(x != y) low = mid;
else{
if(lineweight[x] == -1 or lineweight[x] > mid) low = mid;
else high = mid;
}
}
return (high == 1e9+1)? -1 : high;
}
