#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pil = pair<int, lint>;
using pli = pair<lint, int>;
const int MAX_N = 2e5 + 5;
const lint INF = 5e18;
int n, x, y;
lint k;
vector<pil> adj[MAX_N];
bool seen[MAX_N];
lint min_dist[MAX_N];
priority_queue<pli, vector<pli>, greater<pli>> order;
void dijk(int s) {
for (int i = 0; i <= n - 1; i++) {
min_dist[i] = INF;
seen[i] = false;
}
min_dist[s] = 0;
order.push({0, s});
while (order.size()) {
int u = order.top().second;
order.pop();
if (seen[u]) continue;
seen[u] = true;
for (pil e : adj[u]) {
lint new_dist = min_dist[u] + e.second;
if (new_dist >= min_dist[e.first]) continue;
min_dist[e.first] = new_dist;
order.push({new_dist, e.first});
}
}
}
lint x_dist[MAX_N], y_dist[MAX_N];
lint x_sum[MAX_N], y_sum[MAX_N];
lint find_x_sum(int l, int r) {
if (!(0 <= l && l < n && 0 <= r && r < n)) return 0;
if (l > r) return 0;
return x_sum[r] - ((l == 0) ? 0 : x_sum[l - 1]);
}
lint find_y_sum(int l, int r) {
if (!(0 <= l && l < n && 0 <= r && r < n)) return 0;
if (l > r) return 0;
return y_sum[r] - ((l == 0) ? 0 : y_sum[l - 1]);
}
void precomp() {
dijk(x);
for (int i = 0; i <= n - 1; i++) x_dist[i] = min_dist[i];
dijk(y);
for (int i = 0; i <= n - 1; i++) y_dist[i] = min_dist[i];
for (int i = 0; i <= n - 1; i++)
x_sum[i] = x_dist[i] + ((i == 0) ? 0 : x_sum[i - 1]);
for (int i = 0; i <= n - 1; i++)
y_sum[i] = y_dist[i] + ((i == 0) ? 0 : y_sum[i - 1]);
}
int bin_search(int l, int r) {
int lo = l, hi = r;
while (lo != hi) {
int mid = (lo + hi) / 2;
if (x_dist[mid] >= y_dist[mid]) hi = mid;
else lo = mid + 1;
}
return (x_dist[lo] >= y_dist[lo]) ? lo : r + 1;
}
void init() {
for (int i = 0; i <= n - 1; i++) {
adj[i].clear();
}
}
int max_score(int tmp_n, int tmp_x, int tmp_y, lint tmp_k, vector<int> edge1, vector<int> edge2, vector<int> edge3) {
n = tmp_n;
x = tmp_x;
y = tmp_y;
assert(x < y);
k = tmp_k;
init();
for (int i = 0; i <= n - 2; i++) {
adj[edge1[i]].push_back({edge2[i], edge3[i]});
adj[edge2[i]].push_back({edge1[i], edge3[i]});
}
precomp();
int ans = 0;
for (int x_l = 0; x_l <= n - 1; x_l++) {
for (int x_r = x_l; x_r <= n - 1; x_r++) {
for (int y_l = 0; y_l <= n - 1; y_l++) {
for (int y_r = y_l; y_r <= n - 1; y_r++) {
if (!(x_l <= x && x <= x_r)) continue;
if (!(y_l <= y && y <= y_r)) continue;
if (x_r > y_r || y_l < x_l) continue;
if (x_r < y_l) {
lint cost = find_x_sum(x_l, x_r) + find_y_sum(y_l, y_r);
if (cost > k) continue;
ans = max(ans, x_r - x_l + 1 + y_r - y_l + 1);
continue;
}
int i = bin_search(y_l, x_r);
lint cost = find_x_sum(x_l, y_l - 1) + find_y_sum(y_l, i - 1) + find_x_sum(i, x_r) + find_y_sum(x_r + 1, y_r);
if (cost > k) continue;
ans = max(ans, x_r - x_l + 1 + y_r - y_l + 1);
}
}
}
}
return ans;
}
