P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

给定一个含有 $N$ 个点，$M$ 条边的有向图，点的编号从 $1$ 到 $N$。每条边从 $U_i$ 指向 $V_i$，经过这条边的代价为 $C_i$。图中可能存在重边。 在最开始时，我们可以翻转至多一条边，即让这条边从 $U_i\to V_i$ 永久变为 $V_i\to U_i$，并产生 $D_i$ 的代价。 你要从点 $1$ 到点 $N$，再从点 $N$ 回到点 $1$，你想知道，通过翻转至多一条边，能得到的最小代价和为多少？

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

一行一个整数代表最小代价和。无解输出 $-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)。