Description

$N$ 个模块在双核$C$$P$$U$$（$$A$、$B$$）$中运行。模块$i$ 在核$A$、$B$上的运行成本分别为$a$$_i$ 、$b$$_i$ 。同时，$M$ 对模块需要进行数据交换。若它们在同一个内核上运行，则可以忽略数据交换的成本；否则需要额外的费用。如何安排把总成本降到最低？

Input

第$1$行有两个整数$N$ 和$M$ $（$$1$$≤$$N$ $≤$$2$$0$$0$$0$$0$，$1$$≤$$M$$≤$$2$$0$$0$$0$$0$$0$$）$。接下来的$N$ 行，每行都包含两个整数$a$$_i$ 、$b$$_i$ 。再接下来的$M$ 行，每行都包含三个整数$u$ 、$v$ 、$w$ ，表示若模块$u$ 和模块$v$ 不在同一个内核上执行，则它们之间的数据交换需额外支付$w$ 元。

Output

单行输出最低总成本。

Samples

3 1
1 10
2 10
10 3
2 3 1000

13

来源

POJ3469