JOI 王国共有 $N$ 座城市，编号为 $1$ 到 $N$。共有 $M$ 条连接这些城市的公交线路，编号为 $1$ 到 $M$。第 $i$ 条公交线路（$1 \le i \le M$）从城市 $U_i$ 开往城市 $V_i$，票价为 $C_i$ 日元。对于第 $i$ 条公交线路（$1 \le i \le M$），乘客只能在城市 $U_i$ 上车，且只能在城市 $V_i$ 下车。从一个城市到另一个城市可能有多条公交线路。

奥林匹克运动会即将在 JOI 王国举行。K 总统是 JOI 王国的交通大臣。在奥运会开始前，K 总统可以选择至多一条公交线路，并将其方向反转，且不改变其票价。也就是说，如果他选择了第 $i$ 条公交线路（$1 \le i \le M$），那么在奥运会期间，该线路将不再从城市 $U_i$ 开往城市 $V_i$，而是从城市 $V_i$ 开往城市 $U_i$。反转方向的费用为 $D_i$ 日元，由 K 总统支付。为了避免混乱，奥运会期间不允许再次反转方向。

由于 K 总统是交通大臣，在奥运会期间，他将乘坐公交线路在城市 $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$。

数据范围

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

子任务

1. (5 分) $M \le 1000$
2. (11 分) $M$ 是偶数，$U_{2i-1} = U_{2i}$，$V_{2i-1} = V_{2i}$，$C_{2i-1} = C_{2i}$ ($1 \le i \le \frac{M}{2}$)
3. (21 分) $C_i = 0$ ($1 \le i \le 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

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

样例输入 3

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

样例输出 3

2

样例输入 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