#include <bits/stdc++.h>
#define endl "\n"
#define double long double
#define precise(x) \
fixed << setprecision(x)
#ifndef ONLINE_JUDGE
#define debug(var) cerr << (#var) << ": " << var << endl
#else
#define debug(var)
#endif
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T>;
template <class T>
ostream &operator<<(ostream &os, min_heap<T> H)
{
while (!H.empty())
{
os << H.top() << " ";
H.pop();
}
os << endl;
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, max_heap<T> H)
{
while (!H.empty())
{
os << H.top() << " ";
H.pop();
}
os << endl;
return os << "";
}
template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
return os << P.first << " " << P.second;
}
template <class T>
ostream &operator<<(ostream &os, vector<T> arr)
{
for (long long i = 0; i < (long long)arr.size(); i++)
{
os << arr[i] << " ";
}
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, vector<vector<T>> matrix)
{
os << endl;
for (long long i = 0; i < (long long)matrix.size(); i++)
{
for (long long j = 0; j < (long long)matrix[i].size(); j++)
{
os << matrix[i][j] << " ";
}
os << endl;
}
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
for (auto s : S)
{
os << s << " ";
}
return os << "";
}
template <class T>
ostream &operator<<(ostream &os, multiset<T> S)
{
for (auto s : S)
{
os << s << " ";
}
return os << "";
}
template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M)
{
os << endl;
for (auto m : M)
{
os << "key: " << m.first << endl;
os << "value: " << m.second << endl;
}
return os << "";
}
template <class L, class R>
ostream &operator<<(ostream &os, multimap<L, R> M)
{
os << endl;
for (auto m : M)
{
os << m << endl;
}
return os << "";
}
const long long max_n = 2e5 + 10;
vector<vector<long long>> adj;
vector<vector<pair<long long, long long>>> g;
map<long long, multiset<long long>> vals;
long long depth[max_n];
long long arr[max_n];
long long sz[max_n];
long long heavy = -1;
long long K;
long long ans = 1e9;
long long sack_size(long long node, long long cur_depth, long long cur, long long parent = 0)
{
arr[node] = cur;
depth[node] = cur_depth;
sz[node] = 1;
long long max_sz = 0;
for (long long i = 0; i < (long long)g[node].size(); i++)
{
if (g[node][i].first == parent)
{
continue;
}
long long temp = sack_size(g[node][i].first, cur_depth + 1, cur + g[node][i].second, node);
sz[node] += temp;
if (temp > max_sz)
{
max_sz = temp;
swap(adj[node][0], adj[node][i]);
}
}
return sz[node];
}
void sack_add(long long node, long long parent, long long root, long long type)
{
if (type == 0)
{
vals[arr[node]].erase(vals[arr[node]].find(depth[node]));
if (vals[arr[node]].size() == 0)
{
vals.erase(arr[node]);
}
}
else if (type == 1)
{
long long need = K - arr[node] + 2 * arr[root];
if (vals.find(need) != vals.end())
{
long long temp = *vals[need].begin() + depth[node] - 2 * depth[root];
if (ans > temp)
{
ans = temp;
}
}
}
else
{
vals[arr[node]].insert(depth[node]);
}
for (long long i = 0; i < (long long)adj[node].size(); i++)
{
if (adj[node][i] != parent && adj[node][i] != heavy)
{
sack_add(adj[node][i], node, root, type);
}
}
}
void sack_dfs(long long node, long long parent, long long keep)
{
for (long long i = 1; i < (long long)adj[node].size(); i++)
{
if (adj[node][i] != parent)
{
sack_dfs(adj[node][i], node, 0);
}
}
if (sz[node] != 1)
{
sack_dfs(adj[node][0], node, 1);
heavy = adj[node][0];
}
vals[arr[node]].insert(depth[node]);
long long need = K + arr[node];
if (vals.find(need) != vals.end())
{
long long temp = *vals[need].begin() - depth[node];
if (ans > temp)
{
ans = temp;
}
}
for (long long i = 1; i < (long long)adj[node].size(); i++)
{
if (adj[node][i] != parent)
{
sack_add(adj[node][i], node, node, 1);
sack_add(adj[node][i], node, node, 2);
}
}
heavy = -1;
if (!keep)
{
sack_add(node, parent, node, 0);
}
}
int best_path(int N_temp, int K_temp, int (*edge)[2], int *weight)
{
long long N = N_temp;
K = K_temp;
g.resize(N + 1);
adj.resize(N + 1);
for (long long i = 0; i < N - 1; i++)
{
edge[i][0]++;
edge[i][1]++;
g[edge[i][0]].push_back({edge[i][1], weight[i]});
g[edge[i][1]].push_back({edge[i][0], weight[i]});
adj[edge[i][0]].push_back(edge[i][1]);
adj[edge[i][1]].push_back(edge[i][0]);
}
sack_size(1, 1, 1);
sack_dfs(1, 0, 0);
if (ans == 1e9)
{
ans = -1;
}
return ans;
}
// long long32_t main()
// {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// long long no_of_testcases = 1;
// // cin >> no_of_testcases;
// for (long long i = 1; i <= no_of_testcases; i++)
// {
// // cout << "Case #" << i << ": ";
// solve();
// }
// return 0;
// }
