#include<bits/stdc++.h>
//#include "race.h"
using namespace std;
long long n, k;
const long long MAXN=1e5;
vector<long long>tree[MAXN+10];
vector<pair<long long, long long>>tree1[MAXN+10];
long long sz[MAXN+10];
bool marked[MAXN+10];
long long ans=1e9;
void dfs(long long x, long long p)
{
sz[x]=1;
for (auto next:tree[x])
{
if (p==next) continue;
if (marked[next]) continue;
dfs(next, x);
sz[x]+=sz[next];
}
}
long long findcentr(long long x, long long p, long long teksz)
{
for (auto next:tree[x])
{
if (p==next) continue;
if (marked[next]) continue;
if (sz[next]>teksz/2) return findcentr(next, x, teksz);
}
return x;
}
vector<pair<long long, long long>>dists;
void finddist(long long root, long long p, long long x, long long d, long long len)
{
for (auto next:tree1[x])
{
for (auto next:tree1[x])
{
if (marked[next.first] || next.first==p) continue;
dists.push_back({d+next.second, next.first});
finddist(root, x, next.first, d+next.second, len+1);
}
}
return;
}
void decom(long long root, long long p, long long layer)
{
dfs(root, p);
long long centr=findcentr(root, p, sz[root]);
marked[centr]=true;
unordered_map<long long, long long>ma;
ma[0]=0;
for (auto next:tree1[centr])
{
if (!marked[next.first])
{
dists={};
dists.push_back({next.second, 1});
finddist(centr, centr, next.first, next.second, 1);
for (long long i=0; i<dists.size(); i++)
{
if (dists[i].first==k)
{
ans=min(ans, dists[i].second);
continue;
}
if (dists[i].first>k)
{
continue;
}
if (dists[i].first<k && ma[k-dists[i].first]!=0)
{
ans=min(ans, ma[k-dists[i].first]+dists[i].second);
}
}
for (long long i=0; i<dists.size(); i++)
{
if (dists[i].first<k)
{
if (ma[dists[i].first]!=0) ma[dists[i].first]=min(ma[dists[i].first], dists[i].second);
else ma[dists[i].first]=dists[i].second;
}
}
}
}
for (auto next:tree1[centr])
{
if (!marked[next.first]) decom(next.first, centr, layer+1);
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
for (long long i=0; i<n-1; i++)
{
tree1[H[i][0]+1].push_back({H[i][1]+1, L[i]});
tree1[H[i][1]+1].push_back({H[i][0]+1, L[i]});
tree[H[i][1]+1].push_back(H[i][0]+1);
tree[H[i][1]+1].push_back(H[i][0]+1);
}
decom(1, 1, 1);
return ans;
}
