题目描述

谁会不喜欢小猫和树呢？

小猫 Kis 在院子里发现了一棵大树。树共有 $N$ 个点和 $N-1$ 条边，每条边都有一个正整数长度。

我们定义两点之间的距离为它们之间简单路径上所有边长之和。我们还定义一棵树的直径为树上两点间距离的最大值。

为了更容易爬树，Kis 希望通过若干次操作，使这棵树的直径尽可能小。

他最多可以进行 $K$ 次操作。每次操作中，他可以选择一条当前长度非零的边，并将这条边的长度减少 $1$。

请你求出：在最多进行 $K$ 次操作后，这棵树的最小可能直径是多少。

输入格式

第一行包含两个整数 $N, K$。

接下来 $N-1$ 行，每行三个正整数 $u_i, v_i, w_i$，表示一条连接 $u_i$ 和 $v_i$ 的边，其长度为 $w_i$。

输出格式

输出一个整数，表示经过至多 $K$ 次操作后，树的最小可能直径。

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le K \le 10^9$
• $1 \le u_i, v_i \le N$
• $1 \le w_i \le 10^4$

子任务

只有通过某个子任务及其依赖子任务中的所有测试，才能获得该子任务分数。

样例 1

输入

5 6
1 2 5
2 3 4
2 4 3
4 5 2

输出

6

说明

初始树的直径为 $10$。

经过 $5$ 次操作后，可以把树修改为一个直径为 $6$ 的新树，并且即使允许进行 $6$ 次操作，也无法把直径进一步缩小，因此答案为 $6$。

样例 2

输入

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

输出

5

样例 3

输入

5 0
1 2 5
2 3 4
2 4 3
4 5 2

输出

10