题目描述

探险家小 T 好高兴！X 国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小 T 虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！

比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。

如果就这么点限制，那么问题就太简单了，可是举办方又提出了一个条件：不能经过同一条暗道两次。这个条件让大家犯难了。这该怎么办呢？

到了大溶洞口后，小 T 愉悦地发现这个地方他曾经来过，他还记得有哪些暗道，以及通过每条暗道的时间。小 T 现在向你求助，你能帮他算出至少要多少时间才能回到大溶洞吗？

输入格式

第一行两个数 $n,m$ 表示溶洞的数量以及暗道的数量。

接下来 $m$ 行，每行 $4$ 个数 $s,t,w,v$ ，表示一个暗道连接的两个溶洞 $s,t$ ，这条暗道正着走所需要的时间 $w$ ，倒着走所需要的时间 $v$ 。由于溶洞的相对位置不同，$w$ 与 $v$ 可能不同。

输出格式

输出一行一个数 $t$ ，表示最少所需要的时间。

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

8

数据规模与约定

对于 $100\%$ 的数据，保证 $n\le 10^4 , m\le 2\times 10^5 , 1\le w,v \le 10^4$ 。