BZPRO
#2407. 探险
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！
比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。
如果就这么点限制，那么问题就太简单了，可是举办方又提出了一个条件：
不能经过同一条暗道两次
。这个条件让大家犯难了。这该怎么办呢？
到了大溶洞口后，小T愉悦地发现这个地方他曾经来过，他还记得有哪些暗道，以及通过每条暗道的时间。小T现在向你求助，你能帮他算出至少要多少时间才能回到大溶洞吗？
输入格式
第一行两个数
n
，m
表示溶洞的数量以及暗道的数量。
接下来m行，每行4个数
s
、t
、w
、v
，表示一个暗道连接的两个溶洞
s
、t
，这条暗道正着走（
s
à
t
）的所需要的时间
w
，倒着走（
t
à
s
）所需要的时间
v
。由于溶洞的相对位置不同，
w
与
v
可能不同。
输出格式
输出一行一个数t，表示最少所需要的时间。
样例
样例输入
3 3
1 2 2 1
2 3 4 5
3 1 3 2
样例输出
8
数据范围与提示
N<=10000,M<=200000,1<=W,V<=10000
BZPRO