T6.修复教室 (repair)

• 时间限制：$1000ms$ ，空间限制：$512MB$

  题目描述

  一场台风来袭，破环了学校的教室和道路，学校要修复这些教室和道路，学生们踊跃参与。但道路已经被破坏，学校派出了无人机运送学生参加修复工作。 对于一个教室 $i$ ，运送一个学生到达的代价是 $b_i$ ，这个教室需要 $a_i$ 个学生才能完成修复。 对于一条道路 $i$（设为 $u_i$ 到 $v_i$ ），需要 $u_i$ 点和 $v_i$ 点一共有 $w_i$ 个学生才能完成修复。 学生可以沿着修复好的道路前往其它教室或道路协助修复。 请问如何花费最小的代价修复好所有的教室？请注意，可能不需要修复所有的道路。

输入格式

第一行两个数 $n$ 和 $m$，代表教室数和道路数。 接下来 $n$ 行，每行两个数 $ai，bi$ ，含义见题面。 接下来 $m$ 行，每行三个数 $u_i，v_i，w_i$ ，含义见题面。

输出格式

一行一个数，代表最小代价。

样例输入1

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

样例输出1

140

样例解释1

往 $3$ 号教室运送 $10$ 人，代价 $30$ ，修复教室 $3$ ； 往 $1$ 号教室运送 $22$ 人，修复 $1$ 号教室后修复教室 $1$ 到教室 $2$ 的道路，并且修复教室 $2$，代价$110$；总代价$140$。

样例输入2

5 8
3 6
4 7
7 12
5 7
8 4
1 2 10
3 5 6
1 3 17
2 3 4
2 5 15
4 5 20
1 4 13
2 4 15

样例输出2

52

样例输入3

见下发文件repair\repair3.in

样例输出3

见下发文件repair\repair3.ans

数据规模与约定

对于 $30\%$ 数据$n\le 5，m\le 10$ 。 对于 $60\%$ 数据$n\le 2000，m\le 4000$ 。 对于 $100\%$ 数据$n\le 10^5，m\le 3 \times 10^5，0\le a_i，b_i\le 10^6，0\le c_i\le 10^6$ 。