#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map
vector<pii> q[200100];
int pos[200100];
vector<int> h;
int n, m, timer=0;
int p[200100], sz[200100];
int bcl[200100];
int dsz[200100];
int jmp[100100][20], mx[100100][20];
vector<int> d[200100];
int tin[200100], tout[200100];
int get(int a){
if(p[a] == a) return a;
return p[a] = get(p[a]);
}
void un(int a, int b, int cl){
int ok = 0;
if(bcl[get(a)] != 0 or bcl[get(b)] != 0) ok = 1;
dsz[a] ++;
dsz[b] ++;
if(dsz[b] > 2 or dsz[a] > 2) ok = 1;
if(get(a) == get(b)) ok = 1;
a = get(a);
b = get(b);
if(a == b){
// cout<<"ASDasdasd\n";
while(d[a].size()){
// cout<<a<<'\n';
bcl[d[a].back()] = cl;
d[a].pop_back();
}
return;
}
if(sz[a] < sz[b]) swap(a, b);
if(ok){
while(d[a].size()){
bcl[d[a].back()] = cl;
d[a].pop_back();
}
while(d[b].size()){
bcl[d[b].back()] = cl;
d[b].pop_back();
}
}
while(d[b].size()){
d[a].pb(d[b].back());
d[b].pop_back();
}
p[b] = a;
sz[a] += sz[b];
}
void dfs(int v, int p){
// pos[v] = 1;
tin[v] = ++timer;
for(pii g: q[v]){
int to = g.ff;
int e = g.ss;
if(to == p) continue;
jmp[to][0] = v;
mx[to][0] = e;
dfs(to, v);
}
tout[v] = ++ timer;
}
bool upper(int a, int b){
return (tin[a] <= tin[b] and tout[a] >= tout[b]);
}
int lca(int a, int b){
if(upper(a, b)){
int res = 0;
for(int i = 17; i>=0; i--){
if(upper(jmp[b][i], a)) continue;
res = max(res, mx[b][i]);
b = jmp[b][i];
}
res = max(res, mx[b][0]);
return res;
}
if(upper(b, a)){
// cout<<a<<' '<<b<<'\n';
int res = 0;
for(int i = 17; i>=0; i--){
if(upper(jmp[a][i], b)) continue;
res = max(res, mx[a][i]);
a = jmp[a][i];
}
res = max(res, mx[a][0]);
return res;
}
int res = 0;
for(int i = 17; i>=0; i--){
if(upper(jmp[b][i], a)) continue;
res = max(res, mx[b][i]);
b = jmp[b][i];
}
for(int i = 17; i>=0; i--){
if(upper(jmp[a][i], b)) continue;
res = max(res, mx[a][i]);
a = jmp[a][i];
}
res = max(res, mx[a][0]);
res = max(res, mx[b][0]);
return res;
}
// bool check(int k, int x, int y){
// int mn =
// }
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
vector<vector<int> > dh;
for(int i=0; i<m; i++){
int l = U[i], r = V[i], x = W[i];
dh.pb({x, l, r});
}
for(int i=0; i<n; i++){
sz[i] = 1;
p[i] = i;
d[i].pb(i);
}
sort(dh.begin(), dh.end());
for(auto g: dh){
int x = g[0], l = g[1], r = g[2];
if(get(l) != get(r)){
q[l].pb({r, x});
q[r].pb({l, x});
}
un(l, r, x);
}
// for(int i=0; i<n; i++) cout<<bcl[i]<<' ';
dfs(0, -1);
for(int k=1; k<=17; k++){
for(int i=1; i<=n; i++){
jmp[i][k] = jmp[jmp[i][k-1]][k-1];
mx[i][k] = max(mx[i][k-1], mx[jmp[i][k-1]][k-1]);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
// int l=1, r=1e9 + 1;
// if(!check(r, X, Y)) return -1;
// while(l < r){
// int mid = (l + r)/2;
// if(check(mid, X, Y)) r = mid;
// else l = mid + 1;
// }
if(bcl[X] == 0 or bcl[Y] == 0) return -1;
int mx = max(bcl[X], bcl[Y]);
mx = max(mx, lca(X, Y));
return mx;
}
