问题描述

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。

这棵树共有 $N$ 个节点，编号为 $1$ 至 $N$，树根编号一定为 $1$。

我们用一根树枝两端连接的节点编号描述这一根树枝的位置。

一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量 $Q$，求最多能留住的苹果数量。

（必须要保留根结点，且留下来的树枝必须相连）。

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别表示树的节点数以及要保留的树枝数量。$(1\le Q<N\le 100)$

接下来 $N - 1$ 行描述树枝信息，每行三个整数 $a,b,c$。$a,b$ 是代表两点之间有一根树枝，$c$ 是这根树枝上苹果数量。$(1\le a,b\le N,1\le c\le 10^4)$

输出格式

输出仅一行，表示最多能留住的苹果的数量。

样例输入

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

样例输出

8

说明

你只能保留 $[1,3,2]$，权值和为 $8$。