#include "closing.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#include <vector>
using namespace std;
const int maxn = 2e5 + 10;
const ll inf = (1LL << 60);
set <pair<ll, int> > s;
vector <pair<int, int> > adj[maxn];
vector<pair<ll, int> > v1;
vector<pair<ll, int> > v2;
ll dist[maxn];
int max_score(int n, int a, int b, long long k, vector<int> u, vector<int> v, vector<int> w){
for(int i = 0; i < u.size(); i++){
adj[u[i]].push_back({v[i], w[i]});
adj[v[i]].push_back({u[i], w[i]});
}
s.insert({0, a});
dist[a] = 0;
// v1.push_back({0, 1});
for(int i = 0; i < n; i++){
if(i != a){
s.insert({inf, i});
dist[i] = inf;
}
}
while(!s.empty()){
int x = (*s.begin()).se;
s.erase(s.begin());
if(!v1.empty()) v1.push_back({v1.back().fi + dist[x], v1.size() + 1});
else v1.push_back({0, 1});
for(auto p: adj[x]){
int x2 = p.fi;
int c = p.se;
if(dist[x] + c < dist[x2]){
s.erase({dist[x2], x2});
dist[x2] = dist[x] + c;
s.insert({dist[x2], x2});
}
}
}
s.insert({0, b});
dist[b] = 0;
// v2.push_back({0, 1});
for(int i = 0; i < n; i++){
if(i != b){
s.insert({inf, i});
dist[i] = inf;
}
}
while(!s.empty()){
int x = (*s.begin()).se;
s.erase(s.begin());
if(!v2.empty()) v2.push_back({v2.back().fi + dist[x], v2.size() + 1});
else v2.push_back({0, 1});
for(auto p: adj[x]){
int x2 = p.fi;
int c = p.se;
if(dist[x] + c < dist[x2]){
s.erase({dist[x2], x2});
dist[x2] = dist[x] + c;
s.insert({dist[x2], x2});
}
}
}
v2.push_back({inf, n + 1});
int ans = 0;
for(int i = 0; i < v1.size(); i++){
ll cost = v1[i].fi;
int br = v1[i].se;
// cout << br << ' ' << cost << endl;
if(k - cost < 0) continue;
int p = lower_bound(v2.begin(), v2.end(), make_pair(k - cost + 1, 0)) - v2.begin();
p--;
ans = max(ans, br + v2[p].se);
}
return ans;
}
