#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;
struct DSU{
vector<int> parent, edge_cnt;
vector<bool> swappable;
DSU(int n){
parent = vector<int>(n+1);
iota(all(parent), 0);
edge_cnt = vector<int>(n+1, 0);
swappable = vector<bool>(n+1, false);
}
int find_parent(int p){
return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
}
void merge(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
edge_cnt[a]++;
edge_cnt[b]++;
// Degree >= 3
if(edge_cnt[a] >= 3) swappable[pa] = true;
if(edge_cnt[b] >= 3) swappable[pb] = true;
// Contains cycle
if(pa == pb) swappable[pb] = true;
parent[pa] = pb;
if(swappable[pa]) swappable[pb] = true;
}
bool check(int a, int b){
int pa = find_parent(a);
int pb = find_parent(b);
return (pa == pb && swappable[pa]);
}
};
int _n, _m;
vector<tuple<int, int, int>> edge;
vector<vector<pair<int, int>>> adj(N, vector<pair<int, int>>());
vector<vector<int>> par(N, vector<int>(20)), par_w(N, vector<int>(20));
vector<int> cost(N, inf), tin(N), tout(N);
int timer = 0;
void dfs(int cur, int prev = -1){
tin[cur] = timer++;
for(auto [child, w] : adj[cur]){
if(child == prev) continue;
par[child][0] = cur;
par_w[child][0] = w;
dfs(child, cur);
}
tout[cur] = timer++;
}
void cal_cost1(int cur, int prev = -1){
for(auto [child, w] : adj[cur]){
if(child == prev) continue;
cal_cost1(child, cur);
}
if((int)adj[cur].size() >= 3){
int mn1 = inf, mn2 = inf, mn3 = inf;
for(auto [child, w] : adj[cur]){
if(w < mn1){
mn3 = mn2; mn2 = mn1, mn1 = w;
}else if(w < mn2){
mn3 = mn2; mn2 = w;
}else if(w < mn3){
mn3 = w;
}
}
cost[cur] = mn3;
}
for(auto [child, w] : adj[cur]){
if(child == prev) continue;
cost[cur] = min(cost[cur], max(cost[child], w));
}
}
void cal_cost2(int cur, int prev = -1){
for(auto [child, w] : adj[cur]){
if(child == prev) continue;
cost[child] = min(cost[child], max(cost[cur], w));
cal_cost2(child, cur);
}
}
bool isAnc(int child, int anc){
return (tin[anc] <= tin[child] && tout[anc] >= tout[child]);
}
int get_lca(int a, int b){
int lca = a, cur = a;
for(int i = 19; i >= 0; i--){
int cand = par[cur][i];
if(isAnc(b, cand)){
lca = cand;
}else {
cur = cand;
}
}
return lca;
}
int get_lca_weight(int a, int lca){
int cur = a, val = 0;
for(int i = 19; i >= 0; i--){;
int next_cur = par[cur][i];
if(isAnc(next_cur, lca)){
val = max(val, par_w[cur][i]);
cur = next_cur;
}
}
return val;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
_n = n;
_m = m;
if(m != n-1) return;
// Subtask 4
// for(int i = 0; i < m; i++) edge.PB({w[i], u[i], v[i]});
// sort(all(edge));
// Subtask 5
for(int i = 0; i < m; i++){
u[i]++, v[i]++;
adj[u[i]].PB(MP(v[i], w[i]));
adj[v[i]].PB(MP(u[i], w[i]));
}
par[1][0] = 1;
dfs(1);
for(int i = 1; i < 20; i++){
for(int j = 1; j <= n; j++){
par[j][i] = par[par[j][i-1]][i-1];
par_w[j][i] = max(par_w[j][i-1], par_w[par[j][i-1]][i-1]);
}
}
cal_cost1(1);
cal_cost2(1);
}
// Subtask 3 & 4
// int getMinimumFuelCapacity(int x, int y){
// DSU dsu(_n);
// for(int i = 0; i < _m; i++){
// auto [w, u, v] = edge[i];
// dsu.merge(u, v);
// if(dsu.check(x, y)) return w;
// }
// return -1;
// }
// Subtask 5
int getMinimumFuelCapacity(int x, int y){
x++, y++;
int lca = get_lca(x, y);
int wx = get_lca_weight(x, lca);
int wy = get_lca_weight(y, lca);
return max3(cost[x], wx, wy);
}
