牛牛来到了一个盛产汽水的国度旅行。
这个国度的地图上有 n 个城市,这些城市之间用 n−1 条道路连接,任意两个城市之间,都存在一条路径连接。这些城市生产的汽水有许多不同的风味,在经过道路 i 时,牛牛会喝掉 wi 的汽水。牛牛非常喜欢喝汽水,但过量地饮用汽水是有害健康的,因此,他希望在他旅行的这段时间内,平均每天喝到的汽水的量尽可能地接近给定的一个正整数 k 。
同时,牛牛希望他的旅行计划尽可能地有趣,牛牛会先选择一个城市作为起点,然后每天通过一条道路,前往一个没有去过的城市,最终选择在某一个城市结束旅行。
牛牛还要忙着去喝可乐,他希望你帮他设计出一个旅行计划,满足每天|平均每天喝到的汽水−k|的值尽量小,请你告诉他这个最小值。
输入格式
第一行两个正整数 n,k 。
接下来 n−1 行,每行三个正整数 ui,vi,wi,表示城市 ui 和城市 vi 之间有一条长度为 wi 的道路连接。
同一行相邻的两个整数均用一个空格隔开。
输出格式
一行一个整数,表示 |平均每天喝到的汽水−k| 的最小值的整数部分,即你只要将这个最小值向下取整然后输出即可。
样例一
input
5 21 1 2 9 1 3 27 1 4 3 1 5 12
output
1
explanation
在图中,路径5->1->3是一条最合适的路线,总计喝到的汽水的量是 27+12=39, 平均每天喝到的汽水量是 39÷2=19.5, |19.5−21|=1.5,向下取整后得到 1,因此答案是 1。
样例二
见下发文件。
限制与约定
对于 20% 的数据,n≤1000。
对于另外 20% 的数据,保证编号为 i(1≤i≤n−1) 的节点和编号为 i+1 的节点之间连接了一条边。
对于另外 20% 的数据,保证数据是以1为根的完全二叉树(在完全二叉树中,节点 i(2≤i≤n) 和节点 ⌊i÷2⌋ 之间有一条道路)。
对于另外 20% 的数据,保证除节点 1 以外,其他节点和节点 1 之间都有一条道路。
对于 100% 的数据,1≤n≤5×104,0≤wi≤1013,0≤k≤1013。