F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 4398. -- 福慧双修

4398: 福慧双修

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 501  Solved: 272
[Submit][Status][Discuss]

Description

菩萨为行,福慧双修,智人得果,不忘其本。
——唐朠立《大慈恩寺三藏法师传》
有才而知进退,福慧双修,这才难得。
——乌雅氏
如何福慧双修?被太后教导的甄嬛徘徊在御花园当中。突然,她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应:这就是指导她如何福慧双修的! 现在御花园可以看作是有N块区域,M条小路,两块区域之间可通过小路连接起来。现在甄嬛站在1号区域,而她需要在御花园中绕一绕,且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近,因此她最后还是要回到1号区域。由于太后教导她要福慧双修,因此,甄嬛不能走过任何一条她曾经走过的路。但是, 御花园中来往的奴才们太多了,而且奴才们前行的方向也不一样,因此甄嬛在走某条小路的时候,方向不同所花的时间不一定一样。天色快暗了,甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的,输出“-1”。

Input

第一行仅2个正整数n,m,意义如题。
接下来m行每行4个正整数s,t,v,w,其中s,t为小路所连接的两个区域的编号,v为甄嬛从s到t所需的时间,w为甄嬛从t到s所需的时间。数据保证无重边。

Output

仅一行,为甄嬛回到1号区域所需的最短时间,若方案不存在,则输出-1

Sample Input

3 3
1 2 2 3
2 3 1 4
3 1 5 2

Sample Output

8

HINT

[样例解释]

对于第一个数据:路径为1->2->3->1,所需时间为8,而1->3->2->1所花时间为9。因此答案为8.



[数据范围与约定]

对于40%的数据:n<=1,000; m<=5,000

对于100%的数据:1<=n<=40,000; 1<=m<=100,000; 1<=v,w<=1,000

Source

[Submit][Status][Discuss]

HOME Back