#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen(-1e9, 1e8); ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 2e5+5;
const int mod = 1e9+7;
const int mxlogN = 34;
const int mxK = 26;
//const ll inf = 1e18;
const int K = 100000;
struct edge
{
int u,v,w;
int other(int i)
{
return u^v^i;
}
};
edge es[mxN];
bool vis[mxN];
int cc[mxN];
vector<int> adj[mxN];
void init(int i, int p=-1)
{
cc[i]=1;
for(int e:adj[i])
{
int j=es[e].other(i);
if(p==j||vis[j]) continue;
init(j,i);
cc[i]+=cc[j];
}
}
int find_centroid(int i, int n, int p=-1)
{
for(int e:adj[i])
{
int j=es[e].other(i);
if(p==j||vis[j]) continue;
if(cc[j]>n/2) return find_centroid(j,n,i);
}
return i;
}
const int inf=2e6;
int k;
map<int, int> mp;
int solve2(int i, int r, int w, bool edit, int d=1, int p=-1)
{
if(w==k) return d;
if(w>k) return inf;
int ans=inf;
if(!edit)
{
if(mp.count(k-w)) ans=min(ans, d+mp[k-w]);
}
else
{
if(mp.count(w)) mp[w]=min(mp[w], d);
else mp[w]=d;
}
for(int e:adj[i])
{
int j=es[e].other(i);
if(p==j||vis[j]) continue;
ans=min(ans,solve2(j,r,w+es[e].w,edit,d+1,i));
}
return ans;
}
int solve(int i)
{
init(i);
i=find_centroid(i,cc[i]);
vis[i]=1;
int ans=inf;
for(int e:adj[i])
{
int j=es[e].other(i);
if(vis[j]) continue;
ans=min(ans,solve2(j,j,es[e].w,0));
solve2(j,j,es[e].w,1);
}
mp.clear();
for(int e:adj[i])
{
int j=es[e].other(i);
if(vis[j]) continue;
ans=min(ans,solve(j));
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0; i+1<N; i++)
{
int u=H[i][0], v=H[i][1], w=L[i];
es[i]={u,v,w};
adj[u].push_back(i);
adj[v].push_back(i);
}
int ans=solve(0);
if(ans==inf) ans=-1;
return ans;
}
/*
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
int H[n-1][2];
for(int i=0; i+1<n; i++) cin >> H[i][0] >> H[i][1];
int L[n-1];
for(int i=0; i+1<n; i++) cin >> L[i];
cout << best_path(n,k,H,L);
}*/
