Универститет Городского Планирования и Урбанистики решил открыть филиал в Сортмиярске - ещё бы, ведь в городе целых $n$ зданий, соединённых $n - 1$ автомобильными дорогами, и далеко не вдоль каждой из них проложены велодорожки! Нужно исправлять ситуацию!

А пока что нужно выбрать два здания - общагу и здание университета. Проблема в том, что каждый день студенты должны ездить на электробусе от общаги до университета. Когда они только отправляются в путь, их апатия равна $0$. Но когда по пути им попадается дорога без велодорожек, они начинают паниковать, после чего их апатия повышается на $1$ на весь оставшийся день. Точкой невозврата считается апатия, равная $k$ - если апатия студентов превысила этот уровень, то сегодня они уже не смогут нормально учиться.

Помогите деканату понять, сколько у них вариантов выбрать здания общаги и университета так, чтобы по дороге из общаги в университет уровень апатии студентов не превысил $k$. По всем дорогам в Сортмиярске можно ехать в любом направлении, между любыми двумя зданиями существует путь, все длины дорог одинаковые, а электробус со студентами едет по кратчайшему возможному пути.

Входные данные

В первой строке записаны числа $n$ и $k$ ($1 \le n \le 10^5$, $1 \le k \le 2^{15}$) - число зданий в Сортмиярске и точка невозврата апатии.

В следующих $n - 1$ строках записаны числа $u_i$, $v_i$ и $b_i$ ($1 \le u_i$, $v_i \le n, u \ne v$, $0 \le b \le 1$), которые означают существование дороги из здания $u_i$ в здание $v_i$. Если $b_i = 0$, то вдоль этой дороги проложена велодорожка.

Выходные данные

Выведите одно число - количество способов выбрать здание общаги и университета, чтобы уровень апатии студентов не превысил $k$ по дороге из общаги в университет.

Подзадачи