#3118. Orz the MST

内存限制:256 MiB 时间限制:20 Sec

题目描述

给出一个带权的连通无向图,对于其中的每条边i,在原来边权的基础上,其边权每增加1需要付出的代价为Ai,边权每减少1需要付出的代价为Bi,现在指定该图的一棵生成树,求通过修改边权,使得该生成树成为图的一棵最小生成树,需要付出的最少总代价。
 

输入格式

第一行两个正整数N, M,表示图的点数和边数,点以1~N编号;
接下来M行,每行六个正整数Ui, Vi, Wi, FFi, Ai, Bi,表示一条边(Ui, Vi)权为Wi,在原边权基础上增加1的边权代价为Ai,减少1的边权代价为Bi,FFi若为1则表示该边在指定的生成树中,若为0表示不在。数据保证FF值为1的边刚好组成原图的一棵生成树。两点之间可能有多条不同的边,但没有连接同一点的边。
 

输出格式

 
输出一个正整数,表示所需付出的最少总代价。
 

样例

样例输入


			

6 8
1 2 3 1 4 2
1 4 2 0 3 4
2 3 5 1 2 1
2 4 4 1 3 5
3 5 2 0 1 3
3 6 1 0 2 4
4 5 7 1 3 2
5 6 5 1 5 4

样例输出


			

21

数据范围与提示

【Hint】

样例解释:

最优方案为:(1, 4)边权加2,代价6;(3, 5)边权加3,代价3;(3, 6)边权加4,代价8;(4, 5)边权减2,代价4;总代价21。

数据范围:

1<=N<=300, 1<=M, Wi, Ai, Bi<=1000。