题目描述

事情又要从《Tom & Jerry》说起，自从 Tom 发现自己总是抓不住 Jerry，他就决定与 Jerry 和平相处。

Jerry 的 $n$ 个老鼠洞连成了一棵树，按照约定 Tom 需要在树的每条边上放上一些奶酪，具体地：

• 在每条边上放奶酪有不同的难度，在第 $i$ 条边上放奶酪的难度为 $d_i$。
• Jerry 规定了 $m$ 条限制，每一条限制给定两个点 $u,v$ 和一个值 $w$，要求从 $u$ 到 $v$ 的路径上所有边的奶酪数之和至少为 $w$，保证 $u$ 在 $1$ 到 $v$ 的简单路径上。
• Tom 希望放一些奶酪满足 Jerry 的所有限制，设他在第 $i$ 条边放了 $c_i$ 单位奶酪（$c_i$ 是一个非负数），他希望 $\sum d_i\times c_i$ 最小。

你能帮 Tom 算出这个和式的最小值吗？我们可以说明，结果是一个整数。

输入格式

第一行：两个整数 $n,m$，分别表示树的点数和限制的数量。

接下来 $n-1$ 行：每行两个整数 $x,d$，其中第 $i$ 行表示结点 $x,i+1$ 间有一条边（$x\leq i$），$d$ 为这条边的难度。

接下来 $m$ 行：每行三个整数 $u,v,w$，描述一条限制。

输出格式

输出一行，表示答案。

样例输入

3 2
1 5
2 8
1 3 3
2 3 2

样例输出

21

样例解释

Tom 选择在 $1\to 2$ 这条边上放 $1$ 单位奶酪，在 $2\to 3$ 这条边上放 $2$ 单位奶酪。

数据范围

对于 $100\%$ 的数据：$1\leq n\leq 1000$，$1\leq m\leq 4000$，$1\leq d\leq 50$，$1\leq w\leq 1000$，$1\leq x,u,v\leq n$，$u\ne v$。

提示

1. 您的算法可能比您想象的快

2. 评测机可能比您想象的快

3. 上面两条提示可能没有用