#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MN=2e6+10;
long long n,k;
vector<int>r[MN];
vector<pair<int,long long>>r2[MN];
stack<pair<long long,long long>>hmp;
int br[MN];
bool vis[MN];
stack<long long>wh;
unordered_map<long long,long long>hm;
long long fans=LLONG_MAX-1000000000000;
void dfs(int x,int par){
br[x]=1;
for(auto p:r[x]){
if(p==par||vis[p])continue;
dfs(p,x);
br[x]+=br[p];
}
}
void dfs2(int x,int par,int st,long long de,long long pt){
if(pt>k)return;
if(hm[pt]>de||hm[pt]==0)hmp.push({pt,de});
//cout<<x<<" "<<par<<" "<<de<<" "<<k-pt<<" "<<hm[k-pt]<<"\n";
if(k-pt!=0&&hm[k-pt]==0);
else fans=min(fans,hm[k-pt]+de);
for(auto p:r2[x]){
if(p.first==par||vis[p.first])continue;
dfs2(p.first,x,st,de+1,pt+p.second);
}
if(par==st){
//cout<<par<<" "<<x<<"\n\n";
while(hmp.size()){
//cout<<hmp.top().first<<" "<<hmp.top().second<<" "<<hm[hmp.top().first]<<"\n";
if(hm[hmp.top().first]==0){
hm[hmp.top().first]=LLONG_MAX-1000000000000;
wh.push(hmp.top().first);
}
hm[hmp.top().first]=min(hm[hmp.top().first],hmp.top().second);
hmp.pop();
}
}
}
int cent(int x,int par,int n){
for(auto p:r[x]){
if(p==par||vis[p])continue;
if(br[p]>n/2)return cent(p,x,n);
}
return x;
}
void decomp(int x){
while(wh.size()){
hm[wh.top()]=0;
wh.pop();
}
for(auto&p:hm)p.second=0;
dfs(x,-1);
//cout<<br[x]<<" "<<x;
int y=cent(x,-1,br[x]);
dfs2(y,-1,y,0,0);
vis[y]=1;
for(auto p:r[y]){
if(vis[p])continue;
decomp(p);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
for(int i=0;i<n-1;i++){
int x=H[i][0],y=H[i][1],z=L[i];
r[x].push_back(y);
r[y].push_back(x);
r2[x].push_back({y,z});
r2[y].push_back({x,z});
}
decomp(0);
if(fans==LLONG_MAX-1000000000000)return -1;
return fans;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
20 90
0 1 10
1 2 3
2 3 5
3 4 4
4 5 5
5 6 65
6 7 6
7 8 5
8 9 4
9 10 6
10 11 4
11 12 5
12 13 2
13 14 3
14 15 4
15 16 9
16 17 74
17 18 8
18 19 2
0
*/
