#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;
int n;
vector<array<int, 3>> a;
struct Graph{
int idx[100100], deg[300300], val[300300], ans[100100], sz, N;
vector<int> adj[300300];
void init(int n){
N = n;
sz = n;
for (int i=1;i<=n;i++){
idx[i] = i;
deg[i] = 0;
val[i] = INF;
ans[i] = INF;
}
}
int addV(){
assert(sz+1 < 300300);
deg[sz+1] = 0;
val[sz+1] = INF;
return ++sz;
}
void addE(int x, int y){
y = idx[y];
assert(x<=sz && y<=sz);
adj[x].push_back(y);
deg[y]++;
}
void change(int x, int y){
idx[x] = y;
}
void update(int v, int w){
v = idx[v];
val[v] = min(val[v], w);
}
void dfs(int s, int v = INF){
v = min(v, val[s]);
if (s<=N) ans[s] = v;
for (auto &nxt:adj[s]) dfs(nxt, v);
}
void init(){
for (int i=1;i<=sz;i++) if (!deg[i]){
dfs(i);
}
}
}G;
struct DSU2{
int path[100100], mx[100100], deg[100100], isTree[100100];
void init(int n){
G.init(n);
for (int i=0;i<=n;i++){
path[i] = i, mx[i] = 0, deg[i] = 0, isTree[i] = 1;
}
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
bool merge(int s, int v, int w){
deg[s]++, deg[v]++;
int val = max(deg[s], deg[v]);
s = find(s), v = find(v);
if (s==v){
isTree[s] = 0;
mx[s] = max(mx[s], val);
G.update(s, w);
return 0;
}
path[s] = v;
isTree[v] &= isTree[s];
mx[v] = max(mx[v], mx[s]);
mx[v] = max(mx[v], val);
int tmp = G.addV();
G.addE(tmp, s);
G.addE(tmp, v);
G.change(v, tmp);
if (mx[v]>2 || !isTree[v]) G.update(v, w);
return 1;
}
}dsu;
struct TreeManager{
vector<pair<int, int>> adj[100100];
int sz, dep[100100], sp[100100][20], spE[100100][20], visited[100100];
bool flag1 = 0, flag2 = 0;
void init1(int n){
flag1 = 1, flag2 = 0;
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);
visited[i] = 0, dep[i] = 0;
}
}
void add_edge(int s, int e, int w){
assert(flag1 && !flag2);
adj[s].emplace_back(e, w);
adj[e].emplace_back(s, 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]);
}
}
}
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]);
e = sp[e][0];
}
if (s==e) 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];
}
return max(ret, max(spE[s][0], spE[e][0]));
}
}T1;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
T1.init1(n);
dsu.init(n);
for (int i=0;i<M;i++) a.push_back({W[i], U[i]+1, V[i]+1});
sort(a.begin(), a.end());
for (const auto &[w, u, v]:a){
if (dsu.merge(u, v, w)) T1.add_edge(u, v, w);
}
T1.init2();
G.init();
}
int getMinimumFuelCapacity(int X, int Y) {
++X, ++Y;
int ans = T1.queryE(X, Y);
ans = max(ans, G.ans[X]);
return ans==INF?-1:ans;
}
