翻译结果：

JOI国有$N$个城市，编号从1到$N$。此外，有$M$条单向巴士线路连接着城市和城市，它们都有编号从1到$M$。巴士线路$i$（$1 \leq i \leq M$）从城市$U_i$开往城市$V_i$，票价为$C_i$日元。在巴士线路$i$（$1 \leq i \leq M$）上，除了在城市$U_i$乘车和在城市$V_i$下车外，不能在其他地方上车或下车。某些城市之间可能存在多条巴士线路。

JOI国即将举办奥运会。交通部长K决定，在奥运期间选择最多一条巴士线路，并将其行驶方向反转，但不改变票价。也就是说，如果选择了巴士线路$i$（$1 \leq i \leq M$），在奥运期间该巴士线路将不再从城市$U_i$开往城市$V_i$，而是从城市$V_i$开往城市$U_i$。然而，巴士线路$i$的行驶方向反转需要花费$D_i$日元，这笔费用由K支付。并且，为了避免混乱，在奥运期间不能改变巴士线路的行驶方向。

作为交通部长，K计划在奥运期间往返于城市1和城市N之间乘坐巴士线路。通过明智选择行驶方向反转的巴士线路，他希望最小化往返的总票价与行驶方向反转的费用之和。

给定城市的数量和巴士线路的信息，编写一个程序来找出能够最小化城市1和城市N之间往返的总票价与行驶方向反转费用之和的最小值。如果无论如何都无法往返于城市1和城市N之间，则输出-1。

---

输入

输入从标准输入读取，具有以下格式。所有输入值都为整数。

$N$ $M$ $U_1$ $V_1$ $C_1$ $D_1$ $\vdots$ $U_M$ $V_M$ $C_M$ $D_M$

输出

在标准输出中以一行输出城市1和城市N之间往返的总票价与行驶方向反转费用之和的最小值。但是，如果无论如何都无法往返于城市1和城市N之间，则输出-1。

---

约束条件

• $2 \leq N \leq 200$。
• $1 \leq M \leq 50,000$。
• $1 \leq U_i \leq N$ ($1 \leq i \leq M$)。
• $1 \leq V_i \leq N$ ($1 \leq i \leq M$)。
• $U_i \neq V_i$ ($1 \leq i \leq M$)。
• $0 \leq C_i \leq 1,000,000$ ($1 \leq i \leq M$)。
• $0 \leq D_i \leq 1,000,000,000$ ($1 \leq i \leq M$)。

---

子任务

1. (5分) $M \leq 1,000$。
2. (11分) $M$是偶数，$U_{2i − 1} = U_{2i}$，$V_{2i − 1} = V_{2i}$，$C_{2i − 1} = C_{2i}$ ($1 \leq i \leq \frac{M}{2}$)。
3. (21分) $C_i = 0$ ($1 \leq i \leq M$)。
4. (63分) 没有额外的约束条件。

---

输入例子1

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

输出例子1

10

通过反转巴士线路2，并支付费用1日元，从城市1到城市4的最低票价为6，从城市4到城市1的最低票价为3，城市1和城市4之间往返的总票价与行驶方向反转费用之和为10。

无论如何选择巴士线路，都无法使城市1和城市4之间往返的总票价与行驶方向反转费用之和小于10，因此输出10。

---

输入例子2

4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5

输出例子2

10

该输入输出示例满足子任务2的约束条件。

---

输入例子3

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

输出例子3

2

该输入输出示例满足子任务3的约束条件。

---

输入例子4

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

输出例子4

12

不需要反转巴士线路的行驶方向。

---

输入例子5

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

输出例子5

-1

在这个输入示例中，有两条巴士线路从城市4到城市3。