#4398. 福慧双修

题目描述

菩萨为行，福慧双修，智人得果，不忘其本。

----唐朠立《大慈恩寺三藏法师传》

有才而知进退，福慧双修，这才难得。

----乌雅氏

如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有$N$块区域，$M$条小路，两块区域之间可通过小路连接起来。现在甄嬛站在$1$号区域，而她需要在御花园中绕一绕，且至少经过$1$个非$1$号区 域的区域。但是恰好1号区域离碎玉轩最近，因此她最后还是要回到$1$号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出"$-1$"。

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

8

数据范围与提示

[样例解释]

对于第一个数据：路径为$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$