#include<bits/stdc++.h>

using namespace std;



using pii = pair<int, int>;
int n, k;
pii path[1000005];
vector<pii> g[1000005];
bool vis[1000005];
int mini[1000005];
int ans, inf;
int dfs(int u, int p){
    pii child = {0, u};
    int sub = 0;
    for(auto [l, v] : g[u]){
        if(vis[v] || v == p) continue;
        int cur = dfs(v, u);
        sub += cur;
        child = max<pii>(child, {cur, v});
    }
    path[u] = child;
    return sub;
}

vector<pii> cur;

void dist(int u, int p, int prof, int edges){
    if(prof > k || edges >= ans) return;
    int comp = k - prof;
    if(comp >= 0)
        ans = min(ans, edges + mini[comp]);
    cur.emplace_back(prof, edges);
    for(auto [l, v] : g[u]){
        if(vis[v] || v == p) continue;
        dist(v, u, prof + l, edges + 1);
    }
}

vector<pii> child;
void decomp(int u){
    int sub = dfs(u, u);
    int c = u;
    while(path[c].first > sub/2) c = path[c].second;
    vis[c] = true;

    child.clear();
    cur.reserve(sub);
    for(auto [l, v] : g[c]){
        if(vis[v]) continue;
        cur.clear();
        dist(v, c, l, 1);
        child.insert(child.end(), cur.begin(), cur.end());
        for(auto [prof, edges] : cur)
            mini[prof] = min(mini[prof], edges);
    }
    for(auto [prof, edges] : child)
        mini[prof] = inf;

    for(auto [l, v] : g[c])
        if(!vis[v])
            decomp(v);
}

int best_path(int N,int K,int H[][2], int L[]){
    inf = ans = 1000005;
    n = N;
    k = K;
    for(int i = 0; i < inf; i++) mini[i] = inf;
    mini[0] = 0;
    for(int i = 0; i + 1 < n; i++){
        int u = H[i][0], v = H[i][1], c = L[i];
        g[u].emplace_back(c, v);
        g[v].emplace_back(c, u);
    }
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    for(int u = 0; u<n; u++) shuffle(g[u].begin(), g[u].end(), rng);
    decomp(0);
    if(ans >= inf) ans = -1;
    return ans;
}