AT_njpc2017_e 限界集落

[problemUrl]: https://atcoder.jp/contests/njpc2017/tasks/njpc2017_e ゆらふなくんは，山奥にある限界集落の村長である。この限界集落にあるそれぞれの道路には，村の掟によって「縁起の良い通行方向」が決められている。村の掟に背き，縁起の良い通行方向と逆の向きに通行すれば，村民の冷たい視線に晒されてしまうだろう。限界集落は $ N $ 個の土地と，土地と土地をつなぐ $ N-1 $ 本の道路からなり，土地には $ 1,2,...,N $ と番号がつけられている。$ i $ 番目 ($ 1\ ≦\ i\ ≦\ N-1 $) の道路は土地 $ A_i $ と $ B_i $ をつないでおり，その道路の縁起の良い通行方向は土地 $ A_i $ から $ B_i $ の向きである。土地 $ A_i $ と $ B_i $ の間を移動するには $ C_i $ 分の時間がかかる。土地を頂点，道路を辺とする無向グラフとみなしたとき，この無向グラフは連結である。ある土地から別の土地へ移動するには，通る必要があるすべての道についての $ C $ の総和の時間がかかる。 ゆらふなくんは限界集落に学校を作るための土地を選ぼうとしている。登校に長い時間がかかる学生が出てくるような事態は避けたいので，限界集落の中のどの土地からも $ D $ 分以内で登校できる場所に学校を作りたい。また，学生たちが登校中に村民の冷たい視線に晒されてしまうのを防ぐために，いくつかの道路については縁起の良い通行方向を入れ替える必要がある。登校時間の制約を満たす土地の中で，縁起の良い通行方向を変更しなければならない道路の数が最小となるような土地に学校を作りたい。そのような土地に学校を作った時の縁起の良い通行方向の変更回数を求めよ。もし登校時間の制約を満たすような土地が存在しないならば -1 を出力せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ : $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

登校時間の制約を満たす土地の中で，村の掟を変更する回数が最小となるような土地に学校を作るとき，村の掟を変更する回数を出力せよ。登校時間の制約を満たす土地がないときには -1 を出力せよ。

### 制約 - 入力は全て整数である - $ 2\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ A_i,\ B_i\ ≦\ N $ - $ A_i\ ≠\ B_i $ - $ i\ ≠\ j,\ A_i\ =\ A_j,\ B_i\ =\ B_j $ となるものはない - $ i\ ≠\ j,\ A_i\ =\ B_j,\ A_j\ =\ B_i $ となるものはない - $ 0\ ≦\ C_i\ ≦\ 10^3 $ - $ 1\ ≦\ D\ ≦\ 10^9 $ - 村の掟を無視すれば，どの土地からどの土地へもいくつかの道路を通って到達できる。 ### Sample Explanation 1 登校時間の制約を満たしうる土地は2, 4, 5, 6である。これらの土地が制約を満たすために村の掟を変更しなければならない最小の回数は，それぞれ4, 3, 2, 2である。