#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#ifndef ONLINE_JUDGE
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
#endif
vector<vector<pll>> adj;
vector<bool> vis;
vector<ll> siz;
vector<ll> dub,dubw;
map<ll,ll> global,local;
ll res,W;
void DfsDecompose(int node,int par){
siz[node]=1;
for(pll p:adj[node]){
int v=p.fi,w=p.se;
if(!vis[v] && v!=par){
DfsDecompose(v,node);
siz[node]+=siz[v];
}
}
}
void Dfs(int node,int par,int wp){
if(par==-1){
dub[node]=1;
dubw[node]=wp;
}
else{
dub[node]=dub[par]+1;
dubw[node]=dubw[par]+wp;
}
local[dubw[node]]=min((local.count(dubw[node]) ? local[dubw[node]] : INF),dub[node]);
for(pll p:adj[node]){
int v=p.fi,w=p.se;
if(!vis[v] && v!=par){
Dfs(v,node,w);
}
}
}
int Find(int node,int par,int n){
for(pll p:adj[node]){
int v=p.fi,w=p.se;
if(!vis[v] && v!=par && siz[v]>n/2)
return Find(v,node,n);
}
return node;
}
void Decompose(int node){
DfsDecompose(node,-1);
node=Find(node,-1,siz[node]);
vis[node]=true;
//Debug(node);
global.clear();
for(pll p:adj[node]){
int v=p.fi,w=p.se;
if(!vis[v]){
local.clear();
Dfs(v,-1,w);
for(auto p:local){
res=min(res,(global.count(W-p.fi) ? global[W-p.fi] : INF)+p.se);
}
for(auto p:local){
global[p.fi]=min((global.count(p.fi) ? global[p.fi] : INF),p.se);
}
//Debug(v);
//Debug(local);
}
}
res=min(res,(global.count(W) ? global[W] : INF));
for(pll p:adj[node]){
int v=p.fi,w=p.se;
if(!vis[v]) Decompose(v);
}
}
int best_path(int N, int K, int H[][2], int L[]){
adj.resize(N+1); siz.resize(N+1); vis.resize(N+1); dub.resize(N+1); dubw.resize(N+1);
W=K;
for(int i=0;i<N-1;i++){
int u=H[i][0],v=H[i][1],w=L[i];
adj[u].pb({v,w});
adj[v].pb({u,w});
}
res=LINF;
Decompose(0);
return (res>=INF ? -1 : res);
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
3 3
0 1 1
1 2 1
-1
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
