Description

nju在某个周日只开放了124和125两个机房，假设每个机房都可以容纳足够多的学生。料事如神的机房阿姨事先了解到有N个学生要来机房学习，并且预测到由于环境不同，每个学生在124或125学习分别会产生Ai或Bi个bug。同时在N个学生中有M对伴侣（一个人可以和多个人形成伴侣关系，并且不限定伴侣的性别），如果成为伴侣的两人不在一个机房学习，会由于想念对方而犯错，写出额外的bug。阿姨想请你来制定一个计划，使学生们总共产生的bug最少。

Format

Input

第一行有两个整数，N和M(0<N<5000,0<M<100000)。
接下来有N行，每行有两个整数Ai和Bi(0<Ai,Bi<200)，代表每个学生在124或125分别会产生的bug数。
接着有M行，每行有3个整数a,b,w(0<a,b<=N,0<w<200)，表示a与b是伴侣关系，并且每对伴侣会由于不在一个机房学习，两人会总共额外多产生w个bug。

Output

输出一个整数，代表最少的bug数。

Sample 1

Input

3 1
1 10
2 10
10 3
2 3 100

Output

13

Limitation

1s, 131072K for each test case.

Hint

结果在int范围之内。
在M对伴侣之间不会有相同的两人组合重复出现。

Source

Vijos Original