#include "race.h"
#include<bits/stdc++.h>
using namespace std;
long long int rt,sum,n,m,head[500005],query[500005],maxn[500005],siz[500005],judge[100000015],rem[500005],dis[500005],q[500005],edge_num[500005],dis2[500005]; // rt為當前的根，sum為當前子樹大小
long long int mine[10000010];
//rem : 存儲dis的值
int cnt = 0;
long long int T;
bool vis[500005],test[500005];
long long int ans = 1e9;
struct e
{
int to;
int val;
int next;
}edge[500005];
void add(int x,int y,int val)
{
cnt++;
edge[cnt].to = y;
edge[cnt].next = head[x];
edge[cnt].val = val;
head[x] = cnt;
}
void getrt(int now,int fa)
{
siz[now] = 1;maxn[now] = 0;
for(int i=head[now];i!=0;i=edge[i].next)
{
int to = edge[i].to;
if(to == fa || vis[to] == true)continue;
getrt(to,now);
siz[now] += siz[to];
maxn[now] = max(maxn[now],siz[to]);
}
maxn[now] = max(maxn[now],sum - siz[now]);
if(maxn[now] < maxn[rt])rt = now;
return;
}
void getdis(int now,int fa)
{
rem[0]++;
rem[rem[0]] = dis[now];
edge_num[rem[0]] = dis2[now];
for(int i=head[now];i!=0;i=edge[i].next)
{
int to = edge[i].to;
if(to == fa || vis[to] == true)continue;
dis[to] = dis[now] + edge[i].val;
dis2[to] = dis2[now] + 1;
getdis(to,now);
}
}
void calc(int now)
{
mine[0] = 0;int num = 0;
for(int i=head[now];i!=0;i=edge[i].next)
{
int to = edge[i].to;
if(vis[to] == true)continue;
rem[0] = 0;
dis[to] = edge[i].val;
dis2[to] = 1;
getdis(to,now);
//cout<<now<<" "<<to<<endl;
for(int j=rem[0];j>=1;j--)
{
long long int num1 = rem[j];
long long int num2 = edge_num[j];
if(T - num1 >= 0)
{
ans = min(ans,mine[T-num1]+num2);
}
}
for(int j=rem[0];j>=1;j--)
{
num++;
q[num] = rem[j];
if(rem[j] <= T)mine[rem[j]] = min(mine[rem[j]],edge_num[j]);
}
}
for(int i=1;i<=num;i++)
{
if(q[i] <= T)mine[q[i]] = 1e9; //清空，注意，== T是不需要清空的，因為mine[T]就是目標，若清空了則只會留下最後一棵子樹!
}
}
void solve(int now)
{
vis[now] = true;mine[0] = 0;
calc(now);
for(int i=head[now];i!=0;i=edge[i].next)
{
int to = edge[i].to;
if(vis[to] == true)continue;
sum = siz[to];
maxn[rt = 0] = 1e9;
getrt(to,0);
solve(rt);
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
T = K;
for(int i=1;i<=1e7;i++)mine[i] = 1e9;
for(int i=0;i<=n-2;i++)
{
int u,v,w;
u = H[i][0];
v = H[i][1];
w = L[i];
add(u,v,w);
add(v,u,w);
}
maxn[rt] = sum = n;
getrt(1,0);
solve(rt);
if(ans == 1e9)return -1;
else return ans;
}
