AT_joi2020ho_d.オリンピックバス (Olympic Bus)

JOI 国有 $N$ 个城市，编号从 $1$ 到 $N$。此外，有 $M$ 条单向公交线路，编号从 $1$ 到 $M$。第 $i$ 条公交线路（$1 \leq i \leq M$）从城市 $U_i$ 开往城市 $V_i$，票价为 $C_i$ 日元。在第 $i$ 条公交线路上，除了在城市 $U_i$ 上车和城市 $V_i$ 下车外，不能在其他城市上下车。可能存在多条从同一城市出发到同一城市的公交线路。

JOI 国即将举办奥运会。运输大臣 K 理事长打算选择至多一条公交线路，在奥运会期间将其行驶方向反转，且票价不变。也就是说，如果选择了第 $i$ 条公交线路（$1 \leq i \leq M$），那么在奥运会期间，这条线路将从城市 $U_i$ 开往城市 $V_i$ 改为从城市 $V_i$ 开往城市 $U_i$。不过，反转第 $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 \leq N \leq 200$。
• $1 \leq M \leq 50\,000$。
• $1 \leq U_i \leq N$（$1 \leq i \leq M$）。
• $1 \leq V_i \leq N$（$1 \leq i \leq M$）。
• $U_i \neq V_i$（$1 \leq i \leq M$）。
• $0 \leq C_i \leq 1\,000\,000$（$1 \leq i \leq M$）。
• $0 \leq D_i \leq 1\,000\,000\,000$（$1 \leq i \leq M$）。

子任务

1.（5 分）$M \leq 1\,000$。
2.（11 分）$M$ 为偶数，且 $U_{2i-1} = U_{2i}$，$V_{2i-1} = V_{2i}$，$C_{2i-1} = C_{2i}$（$1 \leq i \leq \frac{M}{2}$）。
3.（21 分）$C_i = 0$（$1 \leq i \leq M$）。
4.（63 分）无额外约束。

样例解释 1

如果以 $1$ 的费用反转第 $2$ 条公交线路的方向，则从城市 $1$ 到城市 $4$ 的最小票价为 $6$，从城市 $4$ 到城市 $1$ 的最小票价为 $3$，往返总票价加上反转费用为 $10$。无法使往返总票价与反转费用之和小于 $10$，因此输出 $10$。

样例解释 2

本输入输出样例满足子任务 $2$ 的约束。

样例解释 3

本输入输出样例满足子任务 $3$ 的约束。

样例解释 4

可以不反转任何公交线路。

样例解释 5

在本输入样例中，存在两条从城市 $4$ 到城市 $3$ 的公交线路。

由 ChatGPT 4.1 翻译