#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAXN = 200010;
const int MAXK = 1000010;
int n, k, n_cur, sub[MAXN], best[MAXK], ans = MAXK;
vector<int> graph[MAXN], cost[MAXN];
bool marc[MAXN];
void find_sub(int v, int p)
{
sub[v] = 1;
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
if(u == p || marc[u]) continue;
find_sub(u, v), sub[v] += sub[u];
}
}
int find_centroid(int v, int p)
{
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
if(u == p || marc[u]) continue;
if(2 * sub[u] >= n_cur) return find_centroid(u, v);
}
return v;
}
void dfs(int v, int p, int dist, int depth, bool flag)
{
if(k < dist) return;
if(flag)
{
if(best[dist] == 0) best[dist] = depth;
else best[dist] = min(best[dist], depth);
}
else best[dist] = 0;
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
int c = cost[v][i];
if(u != p && !marc[u]) dfs(u, v, dist + c, depth + 1, flag);
}
}
void dfs2(int v, int p, int dist, int depth)
{
if(k < dist) return;
if(best[k - dist]) ans = min(ans, best[k - dist] + depth);
if(dist == k) ans = min(ans, depth);
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
int c = cost[v][i];
if(u != p && !marc[u]) dfs2(u, v, dist + c, depth + 1);
}
}
void decompose(int v, int p)
{
find_sub(v, p);
n_cur = sub[v];
int c = find_centroid(v, p);
// printf("\nc = %d\n", c - 1);
marc[c] = true;
for(int i = 0; i < (int) graph[c].size(); i++)
{
int u = graph[c][i];
if(u == p || marc[u]) continue;
dfs2(u, c, cost[c][i], 1);
dfs(u, c, cost[c][i], 1, true);
}
// for(int i = 0; i <= k; i++) printf("best[%d] = %d\n", i, best[i]);
dfs(c, c, 0, 0, false);
for(int i = 0; i < (int) graph[c].size(); i++)
{
int u = graph[c][i];
if(!marc[u]) decompose(u, c);
}
}
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 u = h[i][0] + 1;
int v = h[i][1] + 1;
int w = l[i];
graph[u].push_back(v);
graph[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
decompose(1, 1);
return (ans == MAXK) ? -1 : ans;
}
