题目描述

给定一个含有 $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$。

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 回日本情報オリンピック　本選 D オリンピックバス。