/*
Author:Matkap(prefix_sum)
*/
#include "race.h"
#include <bits/stdc++.h>
#include <array>
using namespace std;
#define endl "\n"
#define ar array
#define all(x) x.begin(),x.end()
const int INF = 1e9 + 7 , MOD = 1e9 + 7;
const int mxN = 2e5 + 7, mxK = 2e6 + 7;
vector<ar<int,2>> adj[mxN];
int rem[mxN];
int sub[mxN];
int cnt[mxK];
int ans = INF;
int k1;
vector<int> vec;
int find_subtree_size(int pos,int par = -1)
{
sub[pos] = 1;
for(auto [it, dist] : adj[pos])
{
if(it == par || rem[it]) continue;
sub[pos] += find_subtree_size(it, pos);
}
return sub[pos];
}
int find_centroid(int sub_size, int pos,int par = -1)
{
for(auto [it, dist] : adj[pos])
{
if(it == par || rem[it]) continue;
if(sub[it] > sub_size / 2) return find_centroid(sub_size, it, pos);
}
return pos;
}
void solve(int pos,int par,int cur_path,int mode, int depth = 1)
{
if(cur_path > k1) return;
if(mode == 1) cnt[cur_path] = min(cnt[cur_path], depth), vec.push_back(cur_path);
else ans = min(ans, cnt[k1 - cur_path] + depth);
for(auto [it, dist] : adj[pos])
{
if(rem[it] || it == par) continue;
solve(it,pos,cur_path + dist,mode,depth + 1);
}
}
void build_decomp(int pos)
{
int centroid = find_centroid(find_subtree_size(pos), pos);
//cout << centroid << endl;
rem[centroid] = 1;
vec.clear();
for(auto [it, dist] : adj[centroid])
{
if(!rem[it])
{
solve(it,-1,dist,0);
solve(it,-1,dist,1);
}
}
for(auto it : vec) cnt[it] = INF;
cnt[0] = 0;
for(auto [it, dist] : adj[centroid])
{
if(rem[it]) continue;
build_decomp(it);
}
}
int best_path(int n,int k, int h[][2], int l[])
{
k1 = k;
fill(cnt, cnt + mxK, INF);
cnt[0] = 0;
for(int i = 0;n - 1 > i;i++)
{
adj[h[i][0]].push_back({h[i][1], l[i]});
adj[h[i][1]].push_back({h[i][0], l[i]});
}
build_decomp(0);
if(ans == INF) return -1;
return ans;
}
/*int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int h[1000][2];
int l[1000];
int n;
int k;
cin >> n >> k;
for(int i = 0;n - 1 > i;i++) for(int j = 0;2 > j;j++) cin >> h[i][j];
for(int i = 0;n - 1 > i;i++) cin >> l[i];
cout << best_path(n, k, h, l) << endl;
}*/
