#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;
int n;
vector<int> adj[100100];
struct DSU{
int path[100100];
void init(int n){for (int i=0;i<=n;i++) path[i] = i;}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
bool merge(int s, int v){
s = find(s), v = find(v);
if (s==v) return 0;
path[s] = v;
return 1;
}
};
struct TreeManager{
vector<pair<int, int>> adj[100100];
int sz, dep[100100], sp[100100][20], spE[100100][20], spV[100100][20], visited[100100];
DSU dsu;
bool flag1 = 0, flag2 = 0;
int lca, prv;
void init1(int n){
flag1 = 1, flag2 = 0;
dsu.init(n);
sz = n;
for (int i=0;i<=sz;i++){
adj[i].clear();
fill(sp[i], sp[i]+20, 0);
fill(spE[i], spE[i]+20, INF);
fill(spV[i], spV[i]+20, INF);
visited[i] = 0, dep[i] = 0;
}
}
bool add_edge(int s, int e, int w){
assert(flag1 && !flag2);
if (!dsu.merge(s, e)) return 0;
// printf(" add %d %d %d\n", s-1, e-1, w);
adj[s].emplace_back(e, w);
adj[e].emplace_back(s, w);
return 1;
}
void updateV(int s, int w){
assert(flag1 && !flag2);
// printf(" updateV %d %d\n", s-1, w);
spV[s][0] = w;
}
void dfs(int s, int pa = 0, int paw = INF){
assert(flag1 && flag2);
sp[s][0] = pa;
spE[s][0] = paw;
dep[s] = dep[pa] + 1;
visited[s] = 1;
for (auto &[v, w]:adj[s]) if (!visited[v]) dfs(v, s, w);
}
void init2(){
assert(flag1 && !flag2);
flag2 = 1;
for (int i=1;i<=sz;i++) if (!visited[i]){
dfs(i);
}
for (int j=1;j<20;j++){
for (int i=1;i<=sz;i++){
sp[i][j] = sp[sp[i][j-1]][j-1];
spE[i][j] = max(spE[i][j-1], spE[sp[i][j-1]][j-1]);
spV[i][j] = min(spV[i][j-1], spV[sp[i][j-1]][j-1]);
}
}
}
int queryE(int s, int e){
int ret = -INF;
if (dep[s]!=dep[e]){
if (dep[s] > dep[e]) swap(s, e);
for (int j=19;j>=0;j--) if (dep[s] < dep[sp[e][j]]){
ret = max(ret, spE[e][j]);
e = sp[e][j];
}
ret = max(ret, spE[e][0]);
prv = e;
e = sp[e][0];
}
if (s==e) {lca = s; return ret;}
for (int j=19;j>=0;j--) if (sp[s][j]!=sp[e][j]){
ret = max(ret, spE[s][j]);
ret = max(ret, spE[e][j]);
s = sp[s][j];
e = sp[e][j];
}
lca = sp[s][0];
return max(ret, max(spE[s][0], spE[e][0]));
}
int queryV(int s, int e){
int ret = INF;
if (sp[e][0]==s || sp[s][0]==e) return ret;
if (lca==s) s = prv, e = sp[e][0];
else if (lca==e) s = sp[s][0], e = prv;
else s = sp[s][0], e = sp[e][0];
if (dep[s]!=dep[e]){
if (dep[s] > dep[e]) swap(s, e);
for (int j=19;j>=0;j--) if (dep[s] < dep[sp[e][j]]){
ret = min(ret, spV[e][j]);
e = sp[e][j];
}
ret = min(ret, spV[e][0]);
e = sp[e][0];
}
if (s==e){
ret = min(ret, spV[s][0]);
return ret;
}
for (int j=19;j>=0;j--) if (sp[s][j]!=sp[e][j]){
ret = min(ret, spV[s][j]);
ret = min(ret, spV[e][j]);
s = sp[s][j];
e = sp[e][j];
}
ret = min(ret, min(spV[s][0], spV[e][0]));
s = sp[s][0];
ret = min(ret, spV[s][0]);
return ret;
}
}T1, T2;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
T1.init1(n);
T2.init1(n);
vector<array<int, 3>> a;
for (int i=0;i<M;i++) a.push_back({W[i], U[i]+1, V[i]+1});
sort(a.begin(), a.end());
for (auto &[w, u, v]:a){
adj[u].push_back(w);
adj[v].push_back(w);
if (T1.add_edge(u, v, w)) continue;
// printf(" T2: ");
T2.add_edge(u, v, w);
}
for (int i=1;i<=n;i++){
sort(adj[i].begin(), adj[i].end());
if (adj[i].size() >= 3) T1.updateV(i, adj[i][2]);
}
T1.init2();
T2.init2();
}
int getMinimumFuelCapacity(int X, int Y) {
++X, ++Y;
int ans = T1.queryE(X, Y);
int v1 = T1.queryV(X, Y), v2 = T2.queryE(X, Y);
ans = max(ans, min(v1, v2));
return ans==INF?-1:ans;
}
