[JOI 2020 Final] オリンピックバス

给定一个 $N$ 点 $M$ 边的有向图，每条边从 $U_i$ 指向 $V_i$，经过这条边的代价为 $C_i$。 点编号为 $1$ 到 $N$。 我们可以翻转一条边，即让他从 $U_i$ 指向 $V_i$ 变为从 $V_i$ 指向 $U_i$，这时会有 $D_i$ 的代价产生。 你要从点 $1$ 到点 $N$，再从点 $N$ 回到点 $1$，你想知道，通过翻转一条边，或者不翻转，能得到的最小代价和为多少？

第一行两个整数 $N,M$ 代表点数和边数。 接下来 $M$ 行每行四个整数 $U_i,V_i,C_i,D_i$ 代表一条边。

一行一个整数代表最小代价和。无解输出 $-1$。

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

10

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

10

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

2

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

12

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

-1

### 样例 1 解释 最优解为翻转第二条边，总代价为： - 翻转的代价 $1$。 - 从点 $1$ 到点 $N$ 再返回的最短路径 $1 \to 2 \to 4 \to 3 \to 1$，代价为 $4+2+1+2=9$。 ### 样例 4 解释 不一定需要翻转某条边。 ### 样例 5 解释 从点 $4$ 到点 $3$ 的边有两条。 ### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$M \le 1000$。 - Subtask 2（11 pts）：$M$ 为偶数，且 $U_{2i}=U_{2i-1}$，$V_{2i}=V_{2i-1}$，$C_{2i}=C_{2i-1}$。 - Subtask 3（21 pts）：$C_i=0$。 - Subtask 4（63 pts）：无特殊限制。 对于 $100\%$ 的数据： - $2 \le N \le 200$。 - $1 \le M \le 5 \times 10^4$。 - $1 \le U_i \le N$。 - $1 \le V_i \le N$。 - $U_i \ne V_i$。 - $0 \le C_i \le 10^6$。 - $0 \le D_i \le 10^9$。 ### 说明 翻译自 [第 19 回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [D オリンピックバス](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t4.pdf)。