#P17750. 占领
占领
占领
题目描述
你作为一名K国战术指挥官,接到了攻打邻国G国的指令。G国的交通系统由个城市和条道路组成。
由于交通原因,你的士兵只能空降到G国的城市中。
对于一个城市,在该城市空投一个士兵的代价是,这个城市需要个士兵才能攻占。
对于一条道路(设为到),需要点和点一共有个士兵才能攻占。
你知道,将G国所有的城市攻占下来就是胜利。假设你的士兵非常神勇,不会死亡,并且可以沿着占领过的道路前往其他城市协助占领其他城市或者道路,而你占领过的道路和城市并不会因为士兵前往其他地点而被G国收回。
现在,你需要花费最小的代价来占领G国的所有城市。请注意,不需要占领所有的道路。
输入格式
从标准输入读入。 第一行2个数,和,代表G国的城市数和道路数
接下来行,每行两个数,含义见题面
接下来行,每行三个数,含义见题面
输出格式
输出到标准输出。 一行一个数,代表最小代价。
样例输入
3 2
10 5
20 10
10 3
1 2 22
2 3 200
样例输出
140
样例说明
在号城市空投人,代价
在号城市空投人,攻占完城市后攻占到的道路,并且攻占城市,代价
总代价
数据范围
对于30%数据
对于60%数据
对于100%数据$n\le 100000,m\le 300000,0\le a_i,b_i\le 1000000,0\le w_i\le 1000000$