//chockolateman
#include<bits/stdc++.h>
// #include "race.h"
using namespace std;
const long long INF = 1e15;
int k,s[200005],depth[200005],ans;
long long val[200005];
set<pair<int,int>> adj[200005];
map<int,int> min_d;
void dfs1(int v,int p)
{
s[v] = 1;
for(auto e : adj[v])
{
int u = e.first;
if(u != p)
{
dfs1(u,v);
s[v] += s[u];
}
}
}
int centroid(int v,int p,int n)
{
for(auto e : adj[v])
{
int u = e.first;
if(u != p && 2*s[u] > n)
return centroid(u,v,n);
}
return v;
}
void dfs2(int v,int p,int add)
{
if(add==0)
{
if(min_d.find(k - val[v]) != min_d.end())
ans = min(ans,depth[v] + min_d[k - val[v]]);
}
else
{
if(min_d.find(val[v]) == min_d.end() || min_d[val[v]] > depth[v])
min_d[val[v]] = depth[v];
}
if(v != p)
{
for(auto e : adj[v])
{
int u = e.first;
int w = e.second;
if(u != p)
{
val[u] = val[v] + w;
depth[u] = depth[v] + 1;
dfs2(u,v,add);
}
}
}
else
{
for(auto e : adj[v])
{
int u = e.first;
int w = e.second;
val[u] = val[v] + w;
depth[u] = depth[v] + 1;
dfs2(u,v,0);
dfs2(u,v,1);
}
}
}
void solve(int v)
{
dfs1(v,v);
int n = s[v];
int c = centroid(c,c,n);
depth[c] = 0;
val[c] = 0;
dfs2(c,c,1);
min_d.clear();
vector<pair<int,int>> temp;
for(auto e : adj[c])
temp.push_back(e);
for(auto e : temp)
{
adj[c].erase(e);
int u = e.first;
int w = e.second;
adj[u].erase({c,w});
solve(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int a,b,w,i = 0 ; i < N-1 ; i++)
{
a = H[i][0];
b = H[i][1];
a++;
b++;
w = L[i];
adj[a].insert({b,w});
adj[b].insert({a,w});
}
ans = N+1;
solve(1);
if(ans==N+1)
ans = -1;
return ans;
}
