在字节山（Mt. Byte）脚下有一个洞穴入口。该洞穴由复杂的洞室系统和连接它们的隧道组成。洞穴入口直通一个被称为“前厅”的洞室。隧道之间不会交叉（它们仅在洞室处汇合）。两个洞室之间要么由一条隧道直接相连，要么完全不相连（但可能通过其他洞室到达）。隧道总是连接两个不同的洞室。

现决定举办“字节国国王杯”（King's of Byteotia Cup）竞赛。每位参赛者的目标是选择一条路线穿过洞穴并尽快离开。路线必须至少经过除前厅以外的一个洞室。比赛仅有两条规则：在洞穴中穿行时，每个洞室（前厅除外）最多只能访问一次，同样，每条隧道最多只能穿过一次。

著名的洞穴探险家 Byteala 正在为比赛做准备。Byteala 在洞穴中进行了长时间的训练，并详细掌握了隧道系统的结构。他计算出了每条隧道在每个方向上的通行时间。在洞室内部移动所需的时间可以忽略不计。现在，Byteala 希望计算出一条满足比赛要求且耗时最短的路线（路线的总耗时为组成该路线的所有隧道通行时间之和）。

请帮助 Byteala！编写一个程序，完成以下任务：

• 从标准输入读取洞穴的描述及每条隧道的通行时间；
• 计算出一条符合要求的路线，使得其经过的隧道通行时间之和最小；
• 将计算出的最短路线耗时输出到标准输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 5\,000$，$3 \le m \le 10\,000$），分别表示洞穴中洞室的数量和连接它们的隧道数量，中间用空格隔开。洞室编号从 $1$ 到 $n$。前厅编号为 $1$。接下来的 $m$ 行包含隧道的描述。每行包含四个用空格隔开的整数。四元组 $a, b, c, d$ 表示洞室 $a$ 和 $b$ 之间有一条隧道，从 $a$ 到 $b$ 的通行时间为 $c$，从 $b$ 到 $a$ 的通行时间为 $d$，$1 \le a, b \le n$，$a \ne b$，$1 \le c, d \le 10\,000$。你可以假设满足比赛要求的路线总是存在的。

输出格式

程序应在第一行（也是唯一一行）输出一个整数，即满足比赛条件的路线所需的最短时间。

样例

样例输入 1

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

样例输出 1

6