#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;
const int MAX = 1E5;
const int LOG = 17;
int timer = -1;
int depth[MAX];
int tin[MAX]; int tout[MAX];
int lift[MAX][LOG];
int lift2[MAX][LOG];
int lift3[MAX][LOG];
int dp[MAX];
vector<int> dp2[MAX];
int ind[MAX];
vector<array<int, 2>> adj[MAX];
vector<array<int, 2>> adj2[MAX];
struct DSU {
int n;
vector<int> parent;
DSU(int n) {
this->n = n;
parent.assign(n, -1);
}
int find(int x) {
if(parent[x] < 0) {
return x;
}
parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int px = find(x); int py = find(y);
if(px == py) {
return;
}
if(parent[px] > parent[py]) {
swap(px, py);
}
parent[px] += parent[py];
parent[py] = px;
}
bool sameSet(int x, int y) {
return find(x) == find(y);
}
};
int n; int m;
vector<array<int, 3>> edges;
vector<bool> spanning;
void dfs(int x, int p, int pw) {
lift[x][0] = p;
lift2[x][0] = pw;
tin[x] = ++timer;
lift3[x][0] = INF + 1;
dp[x] = INF + 1;
if(p != -1) {
for(array<int, 2> i : adj2[p]) {
if(i[1] != lift[p][0] && i[1] != x) {
lift3[x][0] = i[0];
break;
}
}
}
for(array<int, 2> i : adj[x]) {
if(i[1] != p) {
depth[i[1]] = depth[x] + 1;
dfs(i[1], x, i[0]);
dp[x] = min(dp[x], max(dp[i[1]], i[0]));
}
}
tout[x] = timer;
int cnt = 0;
for(array<int, 2> i : adj2[x]) {
if(i[1] != p) {
cnt++;
if(cnt >= 2) {
dp[x] = min(dp[x], i[0]);
break;
}
}
}
}
void dfs2(int x, int p, int dpUp) {
vector<array<int, 2>> vals;
vals.push_back({dpUp, p});
for(array<int, 2> i : adj[x]) {
if(i[1] != p) {
vals.push_back({max(dp[i[1]], i[0]), i[1]});
}
}
sort(vals.begin(), vals.end());
dp2[x].resize(adj[x].size());
for(int i = 0; i < adj[x].size(); i++) {
if(adj[x][i][1] != p) {
ind[adj[x][i][1]] = i;
dp2[x][i] = INF + 1;
for(int j = 0; j < vals.size(); j++) {
if(vals[j][1] != adj[x][i][1]) {
dp2[x][i] = vals[j][0];
break;
}
}
int cnt = 0;
for(array<int, 2> j : adj[x]) {
if(j[1] != adj[x][i][1]) {
cnt++;
if(cnt == 2) {
dp2[x][i] = min(dp2[x][i], j[0]);
break;
}
}
}
dfs2(adj[x][i][1], x, max(dp2[x][i], adj[x][i][0]));
}
}
}
bool isAncestor(int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tin[y];
}
int jump(int x, int y) {
for(int i = 0; i < LOG; i++) {
if(y & (1 << i)) {
x = lift[x][i];
}
}
return x;
}
int lca(int x, int y) {
if(depth[x] > depth[y]) {
swap(x, y);
}
y = jump(y, depth[y] - depth[x]);
if(x == y) {
return x;
}
for(int i = LOG - 1; i >= 0; i--) {
if(lift[x][i] != lift[y][i]) {
x = lift[x][i];
y = lift[y][i];
}
}
return lift[x][0];
}
int getMax(int x, int y) {
int ans = 0;
for(int i = 0; i < LOG; i++) {
if(y & (1 << i)) {
ans = max(ans, lift2[x][i]);
x = lift[x][i];
}
}
return ans;
}
int getMin(int x, int y) {
int ans = INF + 1;
for(int i = 0; i < LOG; i++) {
if(y & (1 << i)) {
ans = min(ans, lift3[x][i]);
x = lift[x][i];
}
}
return ans;
}
int getMinimumFuelCapacity(int X, int Y) {
int z = lca(X, Y);
int pathMax = 0;
if(X != z) {
pathMax = getMax(X, depth[X] - depth[z]);
}
if(Y != z) {
pathMax = max(pathMax, getMax(Y, depth[Y] - depth[z]));
}
int minExtraEdge = INF + 1;
if(z != X && z != Y) {
for(array<int, 2> i : adj2[z]) {
if((!isAncestor(i[1], X) && !isAncestor(i[1], Y)) || depth[i[1]] < depth[z]) {
minExtraEdge = i[0];
break;
}
}
} else {
if(X == z) {
int v = jump(Y, depth[Y] - depth[z] - 1);
minExtraEdge = min(minExtraEdge, dp2[X][ind[v]]);
} else {
int v = jump(X, depth[X] - depth[z] - 1);
minExtraEdge = min(minExtraEdge, dp2[Y][ind[v]]);
}
}
if(X != z) {
minExtraEdge = min(minExtraEdge, dp[X]);
if(lift[X][0] != z) {
minExtraEdge = min(minExtraEdge, getMin(X, depth[X] - depth[z] - 1));
}
}
if(Y != z) {
minExtraEdge = min(minExtraEdge, dp[Y]);
if(lift[Y][0] != z) {
minExtraEdge = min(minExtraEdge, getMin(Y, depth[Y] - depth[z] - 1));
}
}
if(m >= n) {
DSU dsu(n);
int lastWeight = INF + 1;
for(int i = 0; i < m; i++) {
if(spanning[i] && isAncestor(z, edges[i][1]) && isAncestor(z, edges[i][2]) && ((isAncestor(edges[i][1], X) && isAncestor(edges[i][2], X)) || (isAncestor(edges[i][1], Y) && isAncestor(edges[i][2], Y)))) {
continue;
}
dsu.unite(edges[i][1], edges[i][2]);
lastWeight = edges[i][0];
if(dsu.sameSet(X, Y)) {
break;
}
}
minExtraEdge = min(minExtraEdge, lastWeight);
}
int ans = max(minExtraEdge, pathMax);
return (ans <= INF ? ans : -1);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N; m = M;
edges.resize(M);
spanning.resize(M);
for(int i = 0; i < M; i++) {
edges[i] = {W[i], U[i], V[i]};
adj2[U[i]].push_back({W[i], V[i]});
adj2[V[i]].push_back({W[i], U[i]});
}
sort(edges.begin(), edges.end());
DSU dsu(N);
for(int i = 0; i < M; i++) {
if(!dsu.sameSet(edges[i][1], edges[i][2])) {
adj[edges[i][1]].push_back({edges[i][0], edges[i][2]});
adj[edges[i][2]].push_back({edges[i][0], edges[i][1]});
dsu.unite(edges[i][1], edges[i][2]);
spanning[i] = true;
}
}
for(int i = 0; i < N; i++) {
sort(adj[i].begin(), adj[i].end());
sort(adj2[i].begin(), adj2[i].end());
}
dfs(0, -1, -1);
dfs2(0, -1, INF + 1);
for(int i = 1; i < LOG; i++) {
for(int j = 0; j < N; j++) {
if(lift[j][i - 1] == -1) {
lift[j][i] = -1;
} else {
lift[j][i] = lift[lift[j][i - 1]][i - 1];
lift2[j][i] = max(lift2[j][i - 1], lift2[lift[j][i - 1]][i - 1]);
lift3[j][i] = min(lift3[j][i - 1], lift3[lift[j][i - 1]][i - 1]);
}
}
}
}
