抢修南理工水道

Time Limit: 10000 ms

Memory Limit: 65535 ms

Description

由于7.7那次大雨,数量巨大的污泥把南理工的大部分下水道给堵塞了,现在,理工大物业要抢修下水道,临时决定,将喷泉广场的积水及时疏通到友谊河里,来解燃眉之急!从喷泉广场(含)到友谊河(含)中间有N(2<=N<=1000)个下水道疏通点,方便的标号为1.。。N,Dij为i到j的距离,物业现在有多年的经验,对于i至j两个疏通点,疏通1单位距离需要花费Cij。值得提醒的是,i到j之间可能出现两条或多条不同的路径。由于最近资金的紧缺,物业需要你帮他们安排一条1-N的疏通线路,使得花费最小!

Input

有多个case,一文件EO有多个case,一文件EOF结束,第一行输入M ,N(M表示有多少条线路,1<=M<=10000)接下来的M行,输入i,j, Dij,Cij,

Output

输出最小花费值,只占一行。

Sample Input

5 5
1 2 10 2
2 3 15 2
3 4 10 2
4 5 2 10
1 5 10 10

Sample Output

90

Hint

Source

JiaYunlong&YangJianjun

提交代码