题目描述

随着越来越多的计算机配备双核CPU，TinySoft公司的首席技术官SetagLilb决定升级他们的拳头产品——SWODNIW。

该程序由 N 个模块组成，每个模块需在某个核心上运行。每个模块在两个核心上的运行成本分别为 A_i（核心1）和 B_i（核心2）。另有 M 组模块存在数据交互：若两个模块运行在不同核心，需额外支付 w 美元通信成本；若在同一核心则无额外开销。请合理分配模块，使总成本最小。

输入格式

第一行两个整数 N（模块数）和 M（交互组数）。
接下来 N 行，每行两个整数 A_i 和 B_i，表示模块 i 在两个核心的运行成本。
随后 M 行，每行三个整数 a, b, w，表示模块 a 和 b 跨核心运行时需支付 w 美元。

输出格式

一个整数，表示最小总成本。

输入样例

3 1  
1 10  
2 10  
10 3  
2 3 1000

输出样例

13

解释：

• 模块1选核心1（成本1），模块2选核心1（成本2），模块3选核心1（成本10）。
• 模块2和3同核心，无需支付1000，总成本=1+2+10=13。若模块3选核心2（成本3），总成本=1+2+3+1000=1006，非最优。

来源

POJ Monthly--2007.11.25, Zhou Dong