汽水

内存限制：512 MiB 时间限制：100 Sec

牛牛来到了一个盛产汽水的国度旅行。这个国度的地图上有n个城市，这些城市之间用n-1条道路连接，任意两个城

市之间，都存在一条路径连接。这些城市生产的汽水有许多不同的风味，在经过道路 i 时，牛牛会喝掉wi的汽水

。牛牛非常喜欢喝汽水，但过量地饮用汽水是有害健康的，因此，他希望在他旅行的这段时间内，平均每天喝到的

汽水的量尽可能地接近给定的一个正整数k。同时，牛牛希望他的旅行计划尽可能地有趣，牛牛会先选择一个城市

作为起点，然后每天通过一条道路，前往一个没有去过的城市，最终选择在某一个城市结束旅行。牛牛还要忙着去

喝可乐，他希望你帮他设计出一个旅行计划，满足每天 |平均每天喝到的汽水-k| 的值尽量小（其中天数至少为1

），请你告诉他这个最小值。

第一行两个正整数n,k。

接下来n-1行，每行三个正整数ui,vi,wi，表示城市ui和城市vi之间有一条长度为wi的道路连接。

n≤5×10^4，0≤wi≤10^13，0≤k≤10^13。

同一行相邻的两个整数均用一个空格隔开。

一行一个整数，表示 |平均每天喝到的汽水-k|的最小值的整数部分

即你只要将这个最小值向下取整然后输出即可。

#4738. 汽水