#include <bits/stdc++.h>
using namespace std;
//#define HOME
#ifndef HOME
#include "race.h"
#endif // HOME
const int MAX_N = 2e5, MAX_K = 1e6;
bool used[1 + MAX_N];
int sz[1 + MAX_N];
vector <pair <int, int>> gr[1 + MAX_N];
int k;
const int INF = 1e9;
void dfs_sz (int node, int par) {
sz[node] = 1;
for (auto it : gr[node]) {
int son = it.first;
if (not used[son] && son != par) {
dfs_sz (son, node);
sz[node] += sz[son];
}
}
}
int get_centroid (int node, int par, int target) {
for (auto it : gr[node]) {
int son = it.first;
if (sz[son] > target && not used[son] && son != par)
return get_centroid (son, node, target);
}
return node;
}
int best[1 + MAX_K];
void add_paths (int node, int par, int sum, int depth, int bound) {
if (sum > bound)
return;
if (best[sum] > depth)
best[sum] = depth;
for (auto it : gr[node]) {
int son = it.first;
int cost = it.second;
if (not used[son] && par != son)
add_paths (son, node, sum + cost, depth + 1, bound);
}
}
int ans;
void query_paths (int node, int par, int sum, int depth, int bound) {
if (sum > bound)
return;
if (best[bound - sum] + depth < ans)
ans = best[bound - sum] + depth;
for (auto it : gr[node]) {
int son = it.first;
int cost = it.second;
if (not used[son] && par != son)
query_paths (son, node, sum + cost, depth + 1, bound);
}
}
void delete_paths (int node, int par, int sum, int bound) {
if (sum > bound)
return;
best[sum] = INF;
for (auto it : gr[node]) {
int son = it.first;
int cost = it.second;
if (not used[son] && par != son)
delete_paths (son, node, sum + cost, bound);
}
}
void solve (int node) {
/// find centroid
dfs_sz (node, -1);
int centroid = get_centroid (node, -1, sz[node] / 2);
best[0] = 0;
/// add
for (auto it : gr[centroid]) {
int son = it.first;
int cost = it.second;
if (not used[son]) {
query_paths (son, centroid, cost, 1, k);
add_paths (son, centroid, cost, 1, k);
}
}
/// delete
delete_paths (centroid, -1, 0, k);
/// go in subtrees
used[centroid] = true;
for (auto it : gr[centroid]) {
int son = it.first;
if (not used[son])
solve (son);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 1; i <= K; i++)
best[i] = INF;
for (int i = 0; i < N - 1; i++) {
int x = H[i][0], y = H[i][1], c = L[i];
gr[x].push_back ({y, c});
gr[y].push_back ({x, c});
}
ans = INF;
solve (0);
if (ans == INF)
ans = -1;
return ans;
}
/**
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
**/
#ifdef HOME
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(2==scanf("%d %d",&N,&K));
for(i=0; i<N-1; i++)
my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = best_path(N,K,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}
#endif // HOME
