#include <bits/stdc++.h>
using namespace std;
#define nline "\n"
using uint = unsigned int;
const int M = 1e9 + 7;
const int M2 = 998244353;
const int INF = 1e9;
const int N = 1e6 + 10;
const double Degree = 57.2958;
int n,k;
int sz[N];
bool dead[N];
int dist[N];
vector<pair<int, int>> g[N];
vector<int> temp;
void prep(int v,int d, int len, int par = -1)
{
if(len > k)return;
dist[len] = min(dist[len], d);
temp.push_back(len);
for(auto &val:g[v])
{
if(val.first == par || dead[val.first])continue;
prep(val.first, d + 1, len + val.second, v);
}
}
int func(int v, int d, int len, int par = -1)
{
if(len > k)return INF;
int ans = d + dist[k - len];
for(auto &val:g[v])
{
if(val.first == par || dead[val.first])continue;
ans = min(ans, func(val.first, d + 1, len + val.second, v));
}
return ans;
}
void dfs(int v, int par=-1)
{
sz[v] = 1;
for(auto &val:g[v])
{
if(val.first != par && !dead[val.first])
{
dfs(val.first, v);
sz[v] += sz[val.first];
}
}
}
int find_centroid(int currSize, int v, int par = -1)
{
for(auto &val:g[v])
if(val.first != par && !dead[val.first] && 2 * sz[val.first] > currSize)
return find_centroid(currSize, val.first, v);
return v;
}
int decompose(int v)
{
dfs(v);
int centorid = find_centroid(sz[v], v);
dead[centorid] = true;
int ans = INF;
temp.clear();
dist[0] = 0;
for(auto &val:g[centorid])
{
if(!dead[val.first])
{
ans = min(func(val.first, 1, val.second, centorid), ans);
prep(val.first, 1, val.second, centorid);
}
}
dist[0] = INF;
set<int> st(temp.begin(),temp.end());
temp.clear();
temp.assign(st.begin(),st.end());
for(auto &val:temp)
dist[val] = INF;
for(auto &val:g[centorid])
if(!dead[val.first])
ans = min(ans, decompose(val.first));
return ans;
}
int best_path(int nn, int K, int H[][2], int* L)
{
n = nn;
k = K;
vector<pair<int, int>> arr;
for(int i=0;i<N;i++)
dist[i] = INF;
for(int i=0;i<n-1;i++)
{
int u,v;
u = H[i][0];
v = H[i][1];
arr.push_back({u,v});
}
int ct = 0;
for(auto &val:arr)
{
int w;
w = L[ct++];
g[val.first].push_back({val.second, w});
g[val.second].push_back({val.first, w});
}
int ans = decompose(0);
if(ans >= INF)
return -1;
else
return ans;
}
