#include "algorithm"
#include "iostream"
#include "numeric"
#include "iomanip"
#include "cstring"
#include "math.h"
#include "bitset"
#include "string"
#include "vector"
#include "ctime"
#include "queue"
#include "stack"
#include "map"
#include "set"
#include "ext/pb_ds/assoc_container.hpp" // Common file
#include "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include "ext/pb_ds/detail/standard_policies.hpp"
using namespace std;
using namespace __gnu_pbds;
#define f first
#define lgn 25
#define endl '\n'
#define sc second
#define NN (int)2e5+5
#define pb push_back
#define mod 1000000007
#define ld long double
#define mp make_pair
#define vi vector<int>
#define eb emplace_back
#define vpii vector<pii>
#define mii map<int,int>
// #define int long long
#define pii pair<int,int>
#define pq priority_queue
#define BLOCK (int)sqrt(N)
#define test(x) while(x--)
#define all(x) begin(x),end(x)
#define allr(x) rbegin(x),rend(x)
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,n,a) for(int i=n;i>=a;i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define PI acos(-1.0)
#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update >
OS ;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
inline void INP()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
const int inf = 0x3f3f3f3f;
// const int INF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,q,nodes,childs, ans;
string s;
vpii adj[NN];
int Dep[NN] , sz[NN] , Q[NN] , temp[NN] , vis[NN] , path[(int)1e6+100];
void Sz(int i = 1, int p = 0)
{
sz[i] = 1;
nodes++;
for( auto j : adj[i] )
{
if( j.f != p ) Sz( j.f, i ) , sz[i] += sz[j.f];
}
}
int getRoot(int i , int p)
{
for( auto j : adj[i] )
{
if( j.f != p and sz[j.f] > nodes/2 )
{
return getRoot(j.f ,i);
}
}
return i;
}
void getAllDis(int i , int p , int sum , int dep)
{
if( sum > m ) return;
temp[++childs] = sum;
Dep[childs] = dep;
for( auto j : adj[i] )
{
if( j.f != p )
{
getAllDis(j.f , i , sum + j.sc , dep + 1 );
}
}
}
void makeAns(int i , int p )
{
int dn = 0;
vi rmv;
for( auto j : adj[i] )
{
if( j.f != p and !vis[j.f] )
{
childs = 0;
getAllDis(j.f, i, j.sc , 1);
rfo(k,childs,1)
{
int dis = temp[k];
ans = min( ans , path[ m - dis] + Dep[k] );
}
rfo(k,childs,1)
{
rmv.pb( temp[k] );
path[temp[k]] = min( path[temp[k]] , Dep[k] );
}
}
}
for( auto j : rmv ) path[j] = inf;
}
void centroidTree(int i = 1, int p = 0 )
{
nodes = 0;
Sz(i,i);
path[0] = 0;
int centroid = getRoot(i,i);
makeAns(centroid, 0);
vis[i] = 1;
for( auto j : adj[centroid] )
{
if( j.f != p and !vis[j.f] )
{
centroidTree(j.f , centroid);
}
}
}
int go()
{
// cin >> n >> m;
// fo(i,0,n-1)
// {
// int u, v , w;
// cin >> u >> v >> w;
// u++ , v++;
// adj[u].pb({ v, w });
// adj[v].pb({ u, w });
// }
memset( path ,inf , sizeof path );
ans = inf;
centroidTree();
if( ans >= n ) ans = -1;
return ans;
}
int best_path (int N, int K, int H[][2], int L[])
{
n = N, m = K;
fo(i,0,n-1)
{
H[i][0]++;
H[i][1]++;
adj[H[i][0]].pb(mp(H[i][1], L[i]));
adj[H[i][1]].pb(mp(H[i][0], L[i]));
}
return go();
}
// int32_t main()
// {
// INP();
// FAST;
// int t=1;
// // cin>>t;
// test(t) go();
// }
