/**
* Prof.Nicola
**/
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
long k,ans=1e9;
vector<long>len;
vector<pair<pair<long,long>,pair<long,long> > >mn(1e6+1);
struct tree
{
long long n;
vector<vector<pair<long,long> > >edges;
vector<long>depth,sz;
vector<bool>vis;
void scan0(long x,long p,long long l)
{
len[x]=l;
depth[x]=depth[p]+1;
sz[x]=1;
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan0(edges[x][i].F,x,l+edges[x][i].S);
sz[x]+=sz[edges[x][i].F];
}
}
void scan(long x,long p,long long l,long h)
{
if(l<=k){
if(depth[x]<=mn[l].F.F){
if(mn[l].F.S==h){
mn[l].F.F=depth[x];
}
else{
mn[l].S=mn[l].F;
mn[l].F=mp(depth[x],h);
}
}
else if(depth[x]<mn[l].F.S){
if(mn[l].F.S!=h){
mn[l].S=mp(depth[x],h);
}
}
}
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan(edges[x][i].F,x,l+edges[x][i].S,h);
}
}
void scan2(long x,long p,long long l,long h)
{
if(l>k){
return;
}
if(h==mn[k-l].F.S&&mn[k-l].S.S!=0){
ans=min(ans,depth[x]+mn[k-l].S.F);
}
else if(h!=mn[k-l].F.S){
ans=min(ans,depth[l]+mn[k-l].F.F);
}
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan2(edges[x][i].F,x,l+edges[x][i].S,h);
}
}
void scan3(long x,long p,long long l,long h)
{
mn[l]=mp(mp(0,0),mp(0,0));
REP(i,0,edges[x].size()){
if(edges[x][i].F==p||vis[edges[x][i].F]){
continue;
}
scan3(edges[x][i].F,x,l+edges[x][i].S,h);
}
}
long centroid(long x,long p,long z)
{
long mx=0,node=x;
REP(i,0,edges[x].size()){
if(!vis[edges[x][i].F]&&edges[x][i].F!=p&&sz[edges[x][i].F]>mx){
mx=sz[edges[x][i].F];
node=edges[x][i].F;
}
}
if(mx<z){
return x;
}
return centroid(node,x,z);
}
void read(long nodes,vector<vector<pair<long,long> > >e)
{
n=nodes;
edges=e;
}
void build(long long root=1)
{
vis.clear();
vis.resize(n+1);
depth.clear();
depth.resize(n+1);
depth[0]=-1;
sz.clear();
sz.resize(n+1);
scan0(root,0,0);
}
};
tree t;
void solve(long x)
{
t.scan0(x,0,0);
x=t.centroid(x,0,(t.sz[x]+1)/2);
t.vis[x]=true;
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
t.scan(t.edges[x][i].F,0,0,t.edges[x][i].F);
}
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
t.scan2(t.edges[x][i].F,0,0,t.edges[x][i].F);
}
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
t.scan3(t.edges[x][i].F,0,0,t.edges[x][i].F);
}
REP(i,0,t.edges[x].size()){
if(t.vis[t.edges[x][i].F]){
continue;
}
solve(t.edges[x][i].F);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
len.resize(N+1);
vector<vector<pair<long,long> > >e(N+1);
REP(i,0,N-1){
e[H[i][0]].push_back(mp(H[i][1],L[i]));
e[H[i][1]].push_back(mp(H[i][0],L[i]));
}
t.read(N,e);
t.build();
return N;
}
