P6880 [JOI 2020 Final] Olympic Bus

Given a directed graph with $N$ vertices and $M$ edges, the vertices are numbered from $1$ to $N$. Each edge goes from $U_i$ to $V_i$, and the cost to traverse this edge is $C_i$. The graph may contain multiple edges. At the very beginning, you may reverse at most one edge, permanently changing it from $U_i \to V_i$ to $V_i \to U_i$, and paying an additional cost of $D_i$. You need to travel from vertex $1$ to vertex $N$, and then from vertex $N$ back to vertex $1$. You want to know: by reversing at most one edge, what is the minimum possible total cost?

The first line contains two integers $N, M$, representing the number of vertices and the number of edges. The next $M$ lines each contain four integers $U_i, V_i, C_i, D_i$, describing an edge.

Output one integer: the minimum total cost. If there is no solution, output $-1$.

### Explanation for Sample 1 The optimal solution is to reverse the second edge. The total cost is: - The reversing cost is $1$. - The shortest path from vertex $1$ to vertex $N$ and then back is $1 \to 2 \to 4 \to 3 \to 1$, with cost $4+2+1+2=9$. ### Explanation for Sample 4 It is not necessary to reverse any edge. ### Explanation for Sample 5 There are two edges from vertex $4$ to vertex $3$. ### Constraints **This problem uses bundled testdata.** - Subtask 1 (5 pts): $M \le 1000$. - Subtask 2 (11 pts): $M$ is even, and $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): No additional constraints. For $100\%$ of the testdata: - $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$. ### Notes Translated from [The 19th Japanese Olympiad in Informatics, Final Round](https://www.ioi-jp.org/joi/2019/2020-ho/index.html), [D Olympic Bus](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t4.pdf). # Input Format # Output Format # Hint Translated by ChatGPT 5