#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
vector<vector<pair<int, int>>> adj;
vector<int> blocked;
int best = INT32_MAX;
int k;
struct Tree
{
int n = 0;
int centroid = -1;
void spread(int i, int p = -1)
{
n++;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
spread(c, i);
}
}
}
int find_centroid(int i, int p = -1)
{
int subtree_size = 1;
int largest_subtree = 0;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
int sub = find_centroid(c, i);
subtree_size += sub;
largest_subtree = max(largest_subtree, sub);
}
}
if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
centroid = i;
return subtree_size;
}
void dfs(int i, vector<pair<int, int>>& out, int d = 0, int depth = 0, int p = -1)
{
out.push_back({d, depth});
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
dfs(c, out, d + D, depth + 1, i);
}
}
}
vector<int> split()
{
blocked[centroid] = true;
vector<int> out;
for (auto [c, d] : adj[centroid])
{
if (!blocked[c])
out.push_back(c);
}
return out;
}
Tree(int start)
{
spread(start);
if (n <= 1)
return;
find_centroid(start);
assert(centroid != -1);
multiset<pair<int, int>> all;
all.insert({0, 0});
for (auto [c, d] : adj[centroid])
{
vector<pair<int, int>> blub;
dfs(c, blub, d, 1, centroid);
for (auto &[a, b] : blub)
{
int other = k - a;
auto ptr = all.lower_bound({other, 0});
if (ptr != all.end() && ptr->first == other) {
int new_one = b + ptr->second;
best = min(best, new_one);
}
}
for (auto x : blub)
all.insert(x);
}
for (auto x : split()) {
Tree blub(x);
}
}
};
#ifndef _DEBUG
#include "race.h"
#else
int best_path(int N, int K, int H[][2], int L[]);
#endif
int best_path(int N, int K, int H[][2], int L[])
{
adj.resize(N);
blocked.resize(N);
k = K;
for (int i = 0; i < N - 1; i++)
{
adj[H[i][1]].push_back(pair<int, int>{H[i][0], L[i]});
adj[H[i][0]].push_back(pair<int, int>{H[i][1], L[i]});
}
Tree(0);
if (best == INT32_MAX)
return -1;
return best;
}
#ifdef _DEBUG
#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));
}
signed 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
