在遥远的“远得要命王国”（Far Far Away），史莱克（Shrek）和驴子（Donkey）发现自己正漫步在魔法森林中，森林里遍布着由神奇小径连接的魔法草坪。草坪之间由小径相连，每条小径都有一个魔法阻力值。这个阻力值决定了沿特定小径行进的难度。

任意两片草坪之间都有且仅有一条路径，形成了一种称为树的结构。在这个网络中，最难路径（即树的直径）定义为任意两片草坪之间简单路径上阻力值之和的最大值。

像往常一样，驴子想到了一个主意：“史莱克，如果我们给这些小径加点魔法会怎样？”史莱克总是乐于接受新的挑战，他同意了，但知道他们拥有的魔法能量有限——总共正好有 $w$ 个单位。他们必须仔细地将这些额外的魔法分配到各条小径上，以在用尽所有 $w$ 个单位魔法的前提下，尽可能减小网络的直径。

设 $a_i$ 表示第 $i$ 条小径的初始阻力值，他们需要找到新的阻力值 $b_i$，使得：

• $b_i \ge a_i$
• $\sum b_i = w + \sum a_i$
• 每个 $b_i$ 都是整数，因为魔法只能以整数单位施加
• 调整后，魔法草坪网络的直径（任意两片草坪之间最难的路径）被最小化

你能帮他们确定分配魔法的最佳方式吗？

输入格式

第一行包含两个整数 $n$ 和 $w$ —— 草坪的数量和需要分配的魔法能量总量。 接下来的 $n - 1$ 行，每行包含三个整数 $v_i, u_i$ 和 $a_i$ —— 表示草坪 $v_i$ 和 $u_i$ 之间有一条魔法阻力值为 $a_i$ 的小径。

数据范围

$2 \le n \le 2 \cdot 10^5$ $1 \le w \le 10^{12}$ $1 \le u_i, v_i \le n$ $1 \le a_i \le 10^7$ 所有小径构成一棵树。

输出格式

输出一个整数 —— 分配 $w$ 个单位魔法能量后，可能达到的最小直径。

样例

样例输入 1

5 7
1 2 2
1 3 4
1 4 5
3 5 2

样例输出 1

14

样例输入 2

2 7
1 2 4

样例输出 2

11

说明

第一个样例中一种可能的魔法添加方式：

图 1：第一个样例。

在第二个样例中，你必须将 7 加到单条边上。