题目描述

可爱的凯文在高一时就统计了所有人的联系方式，完成了教一的通讯录。每年的寒暑 假开作业大会的时候这张通讯录就充分发挥了作用。同志们根据这张通讯录制定了通讯网络， 可以抽象成一棵树。

每个节点（除叶子节点）首先接受他的所有孩子节点完成的卷子.接着他选择可以完 成任意一张未完成的卷子，也可以选择不做。

最后所有完成的卷子被汇总到树根节点。 很显然做卷子是要消耗时间的，卷子从孩子传到父亲也是要耗时间的。你的任务就是 安排一个计划使得消耗最少时间完成所有卷子并汇总到树根。

输入格式

第一行两个整数 $\red{n，}$$\red{m}$。表示人数和卷子总数。

接下来 $\red{n-1 }$行每行三个整数 $\red{x，}$$\red{y，}$$\red{c}$。表示 $\red{x }$和 $\red{y }$连通，在 $\red{x }$和 $\red{y }$之间传递时间为 $\red{c}$。

最后 $\red{n }$行，每行 $\red{m }$个整数。第 $\red{i }$行第 $\red{j }$列的整数是编号 $\red{i }$的节点完成第 $\red{j }$张卷子消耗 的时间。

$\red{n<=55，}$$\red{m<=11，}$保证 $\red{n>=m}$。根节点的编号为 $\red{1}$。

输出格式

一个整数 $\red{t}$。表示消耗的最小总时间。保证答案在 $\red{longint }$范围内。

样例

输入样例

6 3
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 4 3
3 2 5
6 1 2
1 8 9
8 8 1
4 7 6

输出样例

7

提示

数据说明：

$\red{50\%}$的数据有 $\red{n<=10，}$$\red{m<=5}$。