[POI2004]ZAW

Byte 山脚下有一座洞穴。洞穴由若干洞室和连接洞室的隧道组成，入口通过一条笔直的道路与前厅相连。不同隧道之间不会相交，只会在洞室处相接。整个洞穴系统不一定连通。

这里即将举办“Byteotia 国王杯”比赛。参赛者需要从前厅出发，选择一条路径进入洞穴，并尽快返回前厅。路径除前厅外必须至少经过一个其他洞室。同一个洞室不能被重复经过，前厅除外；同一条隧道也不能被重复经过。

著名洞穴探险家 Byteala 正准备参加这场比赛。经过数月训练，他已经获得了洞穴系统的详细资料。对于每条隧道，他都计算出了沿两个方向通过所需的时间。通过洞室所需的时间可以忽略不计。

请帮助 Byteala 找出一条满足要求且总用时最短的路径。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示洞室数量和隧道数量。洞室编号为 $1$ 到 $n$，其中前厅的编号为 $1$。

接下来 $m$ 行，每行包含四个整数 $a,b,c,d$，表示一条连接洞室 $a$ 与洞室 $b$ 的隧道。从洞室 $a$ 到洞室 $b$ 需要 $c$ 分钟，从洞室 $b$ 到洞室 $a$ 需要 $d$ 分钟。

保证至少存在一条满足要求的路径。

输出格式

输出一行，包含一个整数，表示完成比赛所需的最短时间。

样例输入

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

样例输出

6

数据范围

• $3\le n\le 5\times 10^3$；
• $3\le m\le 10^4$；
• $1\le a,b\le n$，且 $a\ne b$；
• $1\le c,d\le 10^4$；
• 整个洞穴系统不保证连通，但保证至少存在一条满足要求的路径。

来源与许可

本题为 POI 2004 试题「ZAW」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

6