题目描述

江桥在几年前种下了一棵树苗，现在这棵树已经长成了参天大树。。。

具体的，树上共有 $n$ 个结点，这些结点通过 $n - 1$ 条树枝相互连接。其中 $1$ 号结点为根结点。

每条树枝都有一个长度 $l_i$。结点的长度忽略不计。

江桥可以使用魔法将树枝变长。具体的，江桥每花费 $a_i$ 点法力值都可以使第 $i$ 条树枝的长度增加 $1$。

除根结点外，其他只有 $1$ 条树枝连接的结点称为叶子结点。叶子结点的高度即为该结点到根节点中间的所有树枝的长度之和。

江桥想知道，最少需要花多少法力值，才能让所有的叶子结点的高度都相等。

输入格式

第一行两个正整数 $n$，表示树的结点数目。

接下来 $n - 1$ 行，每行三个正整数 $u_i,v_i,l_i$ 表示树中的第 $i$ 条树枝连接了 $u_i,v_i$，长度为 $l_i$。

接下来一行 $n - 1$ 个正整数 $a_i$，表示使第 $i$ 条边变长的花费。

输出格式

一行一个整数表示最少需要花多少法力值才能让所有的叶子结点的高度都相等。

3
1 2 1
1 3 3
1 1

2

样例解释

江桥花费 $2$ 点法力值让第一条树枝长到 $3$ 的长度，这样所有叶子结点的高度均为 $3$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $2 \leq n \leq 5 \times 10^{5},1 \leq u,v \leq n,u \neq v,1 \leq k,l \leq 10^9,1 \leq a_i \leq 10^3$。