该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$C$ 哥建立了一条横跨全球的铁路，方便有长期跨国需求的人通勤。这条铁路有 $n$ 个站点，从 $1$ 到 $n$ 编号，$n-1$ 条线路，其中第 $i$ 条线路在第 $i$ 号站与第 $i+1$ 号站之间通行，单次乘坐需要花费 $a_i$ 元。

除此之外，还可以选择办理 $VIP$ 卡， $n-1$ 条线路的 $VIP$ 系统是独立的，在第 $i$ 号站与第 $i+1$ 号站之间的路线办理 $VIP$ 需要支付 $b_i$ 元，成为 $VIP$ 以后，每次只需要支付 $c_i$ 元即可在 $i$ 号站与第 $i+1$ 号站之间通行。

大 $G$ 在今年有 $m$ 次跨国商务，每次需要从 $d_j$ 站到 $e_j$ 站（如果 $d_j=e_j$ 可以视作不需要乘车）。

大 $G$ 想让你帮它算算，最少花多少钱能完成今年的通勤。

注：原题面格式奇丑无比，$TooY0ung$ 进行了重新的整理和排版。

输入格式

第一行两个正整数 $n$，$m$。

接下来 $n-1$ 行，每行三个正整数表示 $a_i,b_i,c_i$。

接下来 $m$ 行，每行两个正整数，表示 $d_j$ 和 $e_j$。

输出格式

一个正整数，表示大 $G$ 花费的最少价格。

【样例 1 输入】

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

【样例 1 输出】

27

【样例 2 输入】

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

【样例 2 输出】

51

【样例 3 输入】

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

【样例 3 输出】

16

对于$100\%$的数据：$1 \leq a_i,b_i,c_i \leq 10^3$。