#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;
struct DSU{
vector<int> parent, edge_cnt;
vector<bool> swappable;
DSU(int n){
parent = vector<int>(n+1);
iota(all(parent), 0);
edge_cnt = vector<int>(n+1, 0);
swappable = vector<bool>(n+1, false);
}
int find_parent(int p){
return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
}
void merge(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
edge_cnt[a]++;
edge_cnt[b]++;
// Degree >= 3
if(edge_cnt[a] >= 3) swappable[pa] = true;
if(edge_cnt[b] >= 3) swappable[pb] = true;
// Contains cycle
if(pa == pb) swappable[pb] = true;
parent[pa] = pb;
if(swappable[pa]) swappable[pb] = true;
}
bool check(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
return (pa == pb && swappable[pa]);
}
};
int _n, _m;
vector<tuple<int, int, int>> edge;
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++) edge.PB({w[i], u[i], v[i]});
sort(all(edge));
}
int getMinimumFuelCapacity(int x, int y){
DSU dsu(_n);
for(int i = 0; i < _m; i++){
auto [w, u, v] = edge[i];
dsu.merge(u, v);
if(dsu.check(x, y)) return w;
}
return -1;
}
// int main(){
//
// ios::sync_with_stdio(false);
// cin.tie(NULL);
//
// // ifstream cin();
// // ofstream cout();
//
// vector<int> u = {0, 0, 1, 1, 1, 2};
// vector<int> v = {1, 2, 2, 3, 4, 3};
// vector<int> w = {4, 4, 1, 2, 10, 3};
// init(5, 6, u, v, w);
//
// int ans1 = getMinimumFuelCapacity(1, 2);
// int ans2 = getMinimumFuelCapacity(2, 4);
// int ans3 = getMinimumFuelCapacity(0, 1);
// cout << ans1 << endl << ans2 << endl << ans3 << endl;
//
// }
