#include<bits/stdc++.h>
#include "swap.h"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 1e5 + 5;
const int INF = 1e9;
bool is_sub1 = true, is_sub2;
int n, m, u[lim << 1], v[lim << 1], w[lim << 1];
vector<int>ei, g[lim];
namespace sub1{
int max_w;
void init(){
if(m == n){
max_w = *max_element(w, w + m);
}
}
}
namespace sub2{
int third;
void init(){
if(n > 3){
vector<int>p(n - 1);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j){
return w[g[i][0]] < w[g[j][0]];
});
third = p[2];
}
}
}
struct PersistentDSU{
vector<pair<int, int>>parent[lim], max_deg[lim];
int cache_time = -1, size[lim], deg[lim];
void init(){
for(int i = 0; i < n; i++){
parent[i].emplace_back(-(size[i] = 1), i);
max_deg[i].emplace_back(-1, deg[i] = 0);
}
}
int find_set(int N, int time){
while(true){
int par_N = parent[N][upper_bound(parent[N].begin(), parent[N].end(), make_pair(time, INF)) - parent[N].begin() - 1].second;
if(N == par_N){
break;
}
N = par_N;
}
return N;
}
void merge(int u, int v){
int U = u, V = v;
if((u = find_set(u, ++cache_time)) != (v = find_set(v, cache_time))){
if(size[u] < size[v]){
swap(u, v);
}
parent[v].emplace_back(cache_time, u);
size[u] += size[v];
}
int temp = max({max_deg[v].back().second, ++deg[U], ++deg[V]});
if(temp > max_deg[u].back().second){
max_deg[u].emplace_back(cache_time, temp);
}
}
int get_max_deg(int N, int time){
return max_deg[N][upper_bound(max_deg[N].begin(), max_deg[N].end(), make_pair(time, INF)) - max_deg[N].begin() - 1].second;
}
};
PersistentDSU dsu;
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++){
g[u[i] = U[i]].emplace_back(i);
g[v[i] = V[i]].emplace_back(i);
w[i] = W[i];
}
for(int i = 0; i < n; i++){
if(g[i].size() > 2){
is_sub1 = false;
break;
}
}
if(is_sub1){
sub1::init();
return;
}
if(is_sub2 = (*max_element(u, u + m) == 0 && m == n - 1)){
sub2::init();
return;
}
dsu.init();
ei.resize(m);
iota(ei.begin(), ei.end(), 0);
sort(ei.begin(), ei.end(), [&] (int i, int j){
return w[i] < w[j];
});
for(int& i : ei){
dsu.merge(u[i], v[i]);
}
}
int getMinimumFuelCapacity(int x, int y){
if(is_sub1){
return m == n - 1 ? -1 : sub1::max_w;
}
if(is_sub2){
if(x == 0){
return n < 4 ? -1 : max(w[g[y][0]], w[g[sub2::third][0]]);
}
return n < 4 ? -1 : max({w[g[x][0]], w[g[y][0]], w[g[sub2::third][0]]});
}
int low = 0, high = m - 1, ans = -1;
while(low <= high){
int mid = (low + high) >> 1, X = dsu.find_set(x, mid), Y = dsu.find_set(y, mid);
if(X == Y && dsu.get_max_deg(X, mid) > 2){
ans = w[ei[mid]];
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
