由于越来越多的计算机配置了双核CPU，TinySoft公司的首席技术官员SetagLilb决定升级他们的产品——SWODNIW。SWODNIW包含了N个模块，每个模块必须运行在某个CPU中。每个模块在每个CPU中运行的耗费已经被估算出来了，设为Ai和Bi。同时，M对模块之间需要共享数据，如果它们运行在同一个CPU中，共享数据的耗费可以忽略不计，否则，还需要额外的费用。请安排这N个模块，使得总耗费最小。

测试数据的第 1 行为两个整数 N 和 M (1≤N≤20 000，1≤M≤200 000)。接下来有 N 行，每行为两个整数 A_i 和 B_i。接下来有 M 行，每行为 3 个整数 a, b, w，表示 a 模块和 b 模块如果不是在同一个 CPU 中运行，则需要花费额外的 w 耗费来共享数据。

输出一个整数，为最小耗费。