题目描述

译自 JOI 2020 Final T4「オリンピックバス / Olympic Bus」

JOI 王国共有 $N$ 个城市，这些城市从 $1$ 到 $N$ 编号。共有 $M$ 条公交线路连接这些城市，这些线路从 $1$ 到 $M$ 编号。第 $i\ (1\le i\le M)$ 条公交线是从城市 $U_i$ 到城市 $V_i$ 的，票价为 $C_i$ 日元。如果乘客乘坐第 $i$ 条公交线，他只能在城市 $U_i$ 上车，在城市 $V_i$ 下车。从一个城市到另一个城市可能有多条公交线。

不久，JOI 王国将举办奥运会。K 理事长是 JOI 王国交通部部长。他会在奥运会之前选择最多一条公交线，并翻转这条公交线的起点和终点，但不改变票价。换句话说，如果他选择第 $i$ 条公交线，在奥运会期间它将不会从 $U_i$ 城市开往 $V_i$ 城市，而是从 $V_i$ 城市开往 $U_i$ 城市，但票价仍为 $C_i$ 日元。翻转一条公交线需要 $D_i$ 日元，并且这个钱是 K 理事长出的。为了避免迷惑行为，在奥运会期间不允许翻转公交线。

因为 K 理事长是 JOI 王国的交通部部长，在奥运会期间他会使用这些公交线在城市 $1$ 和城市 $N$ 之间往返。通过恰当地选择翻转某条（或不翻转任何）公交线，他想要最小化往返城市 $1$ 和城市 $N$ 的公交总票价与翻转公交线的代价和。

现给定城市数和公交线情况，写一个程序求出这个最小代价和。如果不能通过翻转某条公交线来达到往返城市 $1$ 与城市 $N$ 的目的，请输出 $-1$。

输入格式

第一行两个整数 $N,M$，意义如题目描述；

接下来 $M$ 行，每行四个整数 $U_i,V_i,C_i,D_i$，意义如题目描述。

输出格式

输出一行一个整数，如果可以通过翻转某条（或不翻转任何）公交线使得可以往返于城市 $1$ 与城市 $N$，输出往返所需公交总票价与翻转公交线的代价和的最小值，否则输出 $-1$。

样例 1

input

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

output

10

假设 K 理事长将翻转第二条公交线，这将花费 $1$ 日元，那么从城市 $1$ 到城市 $4$ 的最小花费为 $6$ 日元，从城市 $4$ 到城市 $1$ 的最小花费为 $3$ 日元，加上翻转的代价 $1$ 日元，总代价为 $6+3+1=10$ 日元。

因为没有更优的答案了，所以输出 $10$。

样例 2

input

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

output

10

这个样例满足子任务 $2$ 的限制。

样例 3

input

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

output

2

这个样例满足子任务 $3$ 的限制。

样例 4

input

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

output

12

不是一定要翻转某条公交线。

样例 5

input

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

output

-1

在这个样例中，从城市 $4$ 到城市 $3$ 的公交线有两条。

数据范围与提示

对于全部数据，$2\le N\le 200,1\le M\le 5\times 10^4,1\le U_i,V_i\le N,U_i\neq V_i,0\le C_i\le 10^6,0\le D_i\le 10^9$。

详细子任务附加限制与分值如下表：