#include "swap.h"
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);
const int N = 100005;
pii val[N], t[N * 4];
int dep[N], tp[N], id[N], p[N], sub[N], dp1[N], dp2[N];
vector<pii> g[N];
int n, m, timer;
void dfs_sz(int u = 1, int par = 1) {
dp1[u] = dp2[u] = MAX;
if ((int)g[u].size() >= 3) {
dp1[u] = dp2[u] = g[u][2].ff;
}
sub[u] = 1;
p[u] = par;
for (auto to : g[u]) {
if (to.ss == par) continue;
dep[to.ss] = dep[u] + 1;
dfs_sz(to.ss, u);
dp1[u] = min(dp1[u], max(to.ff, dp1[to.ss]));
sub[u] += sub[to.ss];
}
}
void dfs_dp(int u = 1, int par = 1, int cur = 0) {
dp2[u] = min(dp2[u], max(cur, dp2[par]));
vi v;
int sz = 0;
for (auto to : g[u]) {
if (to.ss == par) continue;
++sz;
v.pub(max(dp1[to.ss], to.ff));
}
if (!sz) return;
vi pref(sz), suf(sz);
pref[0] = v[0];
for (int i = 1; i < sz; ++i) {
pref[i] = min(pref[i - 1], v[i]);
}
suf[sz - 1] = v[sz - 1];
for (int i = sz - 2; i >= 0; --i) {
suf[i] = min(suf[i + 1], v[i]);
}
int ind = 0;
for (auto to : g[u]) {
if (to.ss == par) continue;
dp2[to.ss] = dp2[u];
int mn = MAX;
if (ind != 0) mn = min(mn, max(pref[ind - 1], to.ff));
if (ind != sz - 1) mn = min(mn, max(suf[ind + 1], to.ff));
dp2[to.ss] = min(dp2[to.ss], mn);
}
for (auto to : g[u]) {
if (to.ss == par) continue;
dfs_dp(to.ss, u, to.ff);
}
}
void dfs_hld(int u = 1, int top = 1, int cur = 0) {
tp[u] = top;
id[u] = ++timer;
val[id[u]] = { cur,min(dp1[u],dp2[u]) };
int mx = 0, v = -1;
ll curx = 0;
for (auto to : g[u]) {
if (to.ss == p[u]) continue;
if (sub[to.ss] > mx) {
mx = sub[to.ss];
v = to.ss;
curx = to.ff;
}
}
if (v != -1) dfs_hld(v, top, curx);
for (auto to : g[u]) {
if (to.ss == p[u] || to.ss == v) continue;
dfs_hld(to.ss, to.ss, to.ff);
}
}
void bld(int l = 1, int r = n, int pos = 1) {
if (l == r) {
t[pos] = val[l];
return;
}
int mid = (l + r) / 2;
bld(l, mid, 2 * pos);
bld(mid + 1, r, 2 * pos + 1);
t[pos].ff = max(t[2 * pos].ff, t[2 * pos + 1].ff);
t[pos].ss = min(t[2 * pos].ss, t[2 * pos + 1].ss);
}
int qry(int l, int r, int type, int tl = 1, int tr = n, int pos = 1) {
if (l == tl && r == tr) {
return (type == 1 ? t[pos].ff : t[pos].ss);
}
int mid = (tl + tr) / 2;
if (mid >= r) {
return qry(l, r, type, tl, mid, 2 * pos);
}
if (mid < l) {
return qry(l, r, type, mid + 1, tr, 2 * pos + 1);
}
if (type == 1) {
return max(qry(l, mid, type, tl, mid, 2 * pos), qry(mid + 1, r, type, mid + 1, tr, 2 * pos + 1));
}
return min(qry(l, mid, type, tl, mid, 2 * pos), qry(mid + 1, r, type, mid + 1, tr, 2 * pos + 1));
}
void init(int N, int M, vi U, vi V, vi W) {
n = N, m = M;
for (int i = 0; i < m; ++i) {
++U[i];
++V[i];
g[U[i]].pub({ W[i],V[i] });
g[V[i]].pub({ W[i],U[i] });
}
for (int i = 1; i <= n; ++i) {
sort(all(g[i]));
}
dfs_sz();
dfs_dp();
dfs_hld();
bld();
}
int query1(int x, int y) {
int ret = 0;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
ret = max(ret, qry(id[tp[x]], id[x], 1));
x = p[tp[x]];
}
if (dep[x] > dep[y]) swap(x, y);
if (x == y) return ret;
ret = max(ret, qry(id[x] + 1, id[y], 1));
return ret;
}
int query2(int x, int y) {
int ret = MAX;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
ret = min(ret, qry(id[tp[x]], id[x], 2));
x = p[tp[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ret = min(ret, qry(id[x], id[y], 2));
return ret;
}
int getMinimumFuelCapacity(int X, int Y) {
int x = X, y = Y;
++x, ++y;
int num1 = query1(x, y), num2 = query2(x, y);
if (num2 == MAX) return -1;
return max(num1, num2);
}
/*
15 14
0 1 2
0 2 1
1 3 1
1 4 1
2 5 1
2 6 1
3 7 1
3 8 1
4 9 1
4 10 1
5 11 1
5 12 1
6 13 1
6 14 1
1
*/
