Кількість маршрутів

Є $N$ міст, які пронумеровані числами від $1$ до $N$. Міста сполучені $N$ – $1$ дорогами з двостороннім рухом. Відомо, що між будь-якими двома містами існує шлях напряму, або такий, що проходить через інші міста. На проїзд однієї дороги між парою міст витрачається $1$ одиниця пального. На кожній дорозі є заправна станція, яка дозволяє здійснити заправку на певну кількість одиниць пального.

Машина рухається з міста $A$ в місто $B$ найкоротшим маршрутом, тобто шляхом, що має найменшу кількість доріг. Відомо, що машина здійснює заправку всього один раз (на одній із доріг маршруту) на тій заправній станції, яка забезпечить заправку на максимальну кількість одиниць пального.

Знайдіть кількість пар міст ($A$, $B$), для яких в результаті переїзду з міста $A$ у місто $B$ різниця між придбаним на заправній станції пальним та витраченим на переїзд буде не меншою заданого числа $K$.

Giriş verilənləri

У першому рядку записані два натуральних числа: $N$ та $K$ ($1$ ≤ $N$, $K$ ≤ $100000$).

Далі слідують $N$ – $1$ рядків, у кожному з яких наведено інформацію про дороги, що сполучають міста $X_i$ та $Y_i$ та кількість одиниць пального на заправній станції $C_i$ у формі трьох цілих чисел: $X_i$, $Y_i$ та $C_i$($1$ ≤ $X_i$, $Y_i$ ≤ $N$, $1$ ≤ $i$ ≤ $N$ – $1$, $1$ ≤ $C_i$ ≤ $100000$).

Çıxış verilənləri

Одне ціле число – кількість пар міст ($A$, $B$), для яких в результаті переїзду з міста $A$ у місто $B$ різниця між придбаним на заправній станції пальним та витраченим на переїзд не буде меншою заданого числа $K$.

При цьому пари міст ($1$, $2$) та ($2$, $1$) вважаються різними.

Nümunələr

Qeyd