很久以前，在遥远的星系中，反抗军的一群绝地武士必须摧毁死星。死星由 $n$ 个有守卫的指挥中心和 $m$ 条连接它们的双向通道组成。每条通道连接两个（不一定不同）指挥中心。一对指挥中心之间可能由两条或更多条通道连接。反抗军的目标是占领所有的指挥中心。注意，并不需要占领所有的通道。

对于任意指挥中心 $i$，已知在此处直接传送一名绝地武士所需的资源数 $b_i$（因此，派遣 $k$ 名绝地武士需要消耗 $b_i \cdot k$ 的资源）。要占领指挥中心 $i$，反抗军需要在此处聚集至少 $a_i$ 名绝地武士。要占领通道 $j$，他们需要在这条通道的两个端点累计聚集至少 $c_j$ 名绝地武士。所有的占领行动都不会产生伤亡：没有绝地武士会牺牲，他们都可以继续为占领其他指挥中心和通道而战斗。

在占领一条通道或一个指挥中心后，绝地武士可以通过它免费移动。要占领一个指挥中心，绝地武士可以直接被派遣到那里，或者通过已经占领的通道从其他指挥中心步行走过去。要占领一条通道，绝地武士不需要聚集在同一个指挥中心：他们可以从通道的两个端点同时发起攻击（但前提是两个端点的绝地武士总数至少为 $c_i$）。

求占领所有指挥中心所需的最小资源数。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 300\,000$）—— 分别表示指挥中心和通道的数量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$0 \le a_i, b_i \le 1\,000\,000$）—— 分别表示占领第 $i$ 个指挥中心所需的最小绝地武士数量，以及直接向第 $i$ 个指挥中心派遣一名绝地武士所需的资源量。

接下来的 $m$ 行描述通道。每行包含三个整数 $s_i$、$f_i$ 和 $c_i$（$1 \le s_i, f_i \le n$，$0 \le c_i \le 1\,000\,000$）—— 分别表示第 $i$ 条通道连接的两个指挥中心的编号，以及占领第 $i$ 条通道所需的最小绝地武士数量。

输出格式

输出一个整数：占领死星所有指挥中心所需的最小资源数。

样例

输入样例 1

3 2
10 5
20 10
10 3
1 2 22
2 3 200

输出样例 1

140