caravane

 

В Сахара има N оазиса, съединени с пътища, така че от всеки оазис може да се отиде до всеки друг и това става по единствен начин (по единствен път или по единствена последователност от пътища). За някои двойки оазиси през годината се организират по два кервана, съответно в едната и в другата посока. Условието да има организиран керван между два оазиса е пътуването да може да се осъществи чрез преминаване по точно K пътя. Така, ако пътуването между  два оазиса се извършва по пътища, чийто брой е различен от K, за тази двойка оазиси не се организират кервани. Главният халиф решил да въведе такси, които всеки керван да плаща при ползване на всеки от пътищата. Халифът искал да знае общата сума от таксите, събрани през годината.

Вход
Входният файл
caravane.in съдържа в първия си ред броя на градовете N и стойността K. Следващите N-1 реда съдържат по три числа, разделени с интервали: x, y и t, които показват, че съществува път между оазисите x и y, и таксата за минаването по този път е t.

Изход
Изходният файл
caravane.out трябва да съдържа един ред с търсената обща сума на таксите.

Ограничения
1 < N < 100 000
0 < K < 32
Таксата за всеки път е положително цяло число
<= 100
Стойността на общата сума на събраните такси изисква за записването си 8-байтово цяло число със знак.

Пример

caravane.in

caravane.out

Обяснение

5 2
4 2 11
5 4 3
3 2 5
2 1 4

108

Кервани са организирани само между двойките оазиси: 1-3, 1-4, 2-5, 3-1, 3-4, 4-1, 4-3 и 5-2, съответно с такси 9, 15, 14, 9, 16, 15, 16, и 14. Общата сума на тези такси е 108.

Време за работа на програмата: 0.6 секунди за тест.
Обща разрешена памет: 30
MB, от която 1 MB за стек.

student Gheroghe Stefan
A.S.E. Bucharest
stefangh@gmail.com

Превод на български: Емил Келеведжиев