#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N,M;
const int mxN = 100001;
vector<array<int,3>> edges;
vector<int> parent(mxN,-1);
vector<int> iscycle(mxN,0);
vector<int> adj[mxN];
vector<int> cur_chain;
vector<int> chain;
vector<int> vis(mxN,0);
void dfs(int node,int en){
vis[node]=true;
cur_chain.push_back(node);
if(en==node){
chain=cur_chain;
}
for(int u : adj[node]){
if(!vis[u])
dfs(u,en);
}
cur_chain.pop_back();
}
int find(int node){
if(node==parent[node])
return node;
return parent[node]=find(parent[node]);
}
void unite(int a,int b){
a=find(a),b=find(b);
if(a==b){
iscycle[a]=true;
return;
}
iscycle[a]|=iscycle[b];
parent[b]=a;
}
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.push_back({W[i],U[i],V[i]});
}
sort(edges.begin(),edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
for(int i=0;i<N;i++){
parent[i]=i;
iscycle[i]=false;
adj[i].clear();
vis[i]=0;
}
chain.clear();
if(X>Y)
swap(X,Y);
vector<int> inchain(N,false);
for(int i=0;i<M;i++){
int w=edges[i][0],u=edges[i][1],v=edges[i][2];
if(u>v)
swap(u,v);
unite(u,v);
adj[u].push_back(v);
adj[v].push_back(u);
assert(find(u)==find(v));
if(find(X)==find(Y)&&chain.size()==0){
dfs(X,Y);
for(int node : chain){
inchain[node]=true;
}
for(int j=0;j<=i;j++){
int uu=edges[j][1],vv=edges[j][2];
if(((uu!=X&&uu!=Y)&&(vv!=X&&vv!=Y))&&inchain[uu]!=inchain[vv]){
return w;
}
}
}
if(iscycle[find(X)]&&find(X)==find(Y)){
return w;
}
if(find(X)==find(Y)&&((u!=X&&u!=Y)&&(v!=X&&v!=Y))&&inchain[u]!=inchain[v]){
return w;
}
if(find(X)==find(Y)&&(adj[X].size()>=3||adj[Y].size()>=3)){
return w;
}
}
return -1;
}
