You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是 说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的 总数会远大于九，当然也会有旧头因衰老而自己脱落。

题目描述

有一天，有 $M$ 个脑袋的九头龙看到一棵长有 $N$ 个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把 $N$ 个果子分成 $M$ 组，每组至少有一个果子，让每个头吃一组。

这 $M$ 个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好 $K$ 个果子，而且 $K$ 个果子中理所当然地应该包括唯一的一个最大的果子。果子由 $N-1$ 根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。

对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。

九头龙希望它的“难受值”尽量小，你能帮它算算吗？

例如图 $1$ 所示的例子中，果树包含 $8$ 个果子，$7$ 段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉 $4$ 个果子，其中必须包含最大的果子。即 $N=8$，$M=2$，$K=4$：

图一描述了果树的形态，图二描述了最优策略。

输入格式

输入的第 $1$ 行包含三个整数 $N\ (1 \le N \le 300)$，$M(2 \le M \le N)$，$K(1 \le K \le N)$。$N$ 个果子依次编号 $1,2, \cdots N$，且最大的果子的编号总是 $1$。

第 $2$ 行到第 $N$ 行描述了果树的形态，每行包含三个整数 $a\ (1 \le a \le N), b\ (1 \le b \le N), c\ (0 \le c \le 10^5)$，表示存在一段难受值为 $c$ 的树枝连接果子 $a$ 和果子 $b$。

输出格式

输出仅有一行，包含一个整数，表示在满足“大头”的要求 的前提下，九头龙的难受值的最小值。如果无法满足要求，输出 $-1$。

8 2 4 
1 2 20 
1 3 4 
1 4 13 
2 5 10 
2 6 12 
3 7 15 
3 8 5 

4

提示

该样例对应于题目描述中的例子。