#P17750. 占领

占领

占领

题目描述

你作为一名K国战术指挥官,接到了攻打邻国G国的指令。G国的交通系统由nn个城市和mm条道路组成。

由于交通原因,你的士兵只能空降到G国的城市中。

对于一个城市ii,在该城市空投一个士兵的代价是bib_i,这个城市需要aia_i个士兵才能攻占。

对于一条道路ii(设为uiu_i到viv_i),需要uiu_i点和viv_i点一共有wiw_i个士兵才能攻占。

你知道,将G国所有的城市攻占下来就是胜利。假设你的士兵非常神勇,不会死亡,并且可以沿着占领过的道路前往其他城市协助占领其他城市或者道路,而你占领过的道路和城市并不会因为士兵前往其他地点而被G国收回。

现在,你需要花费最小的代价来占领G国的所有城市。请注意,不需要占领所有的道路。

输入格式

从标准输入读入。 第一行2个数,nn和mm,代表G国的城市数和道路数

接下来nn行,每行两个数ai,bia_i,b_i,含义见题面

接下来mm行,每行三个数ui,vi,wiu_i,v_i,w_i,含义见题面

输出格式

输出到标准输出。 一行一个数,代表最小代价。

样例输入

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

样例输出

140 

样例说明

在33号城市空投1010人,代价3030

在11号城市空投2222人,攻占完城市11后攻占11到22的道路,并且攻占城市22,代价110110

总代价140140

数据范围

对于30%数据n≤5,m≤10n\le 5,m\le 10

对于60%数据n≤2000,m≤4000n\le 2000,m\le 4000

对于100%数据$n\le 100000,m\le 300000,0\le a_i,b_i\le 1000000,0\le w_i\le 1000000$