Description

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?

Input Format

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 Format

Output one integer: the minimum total cost. If there is no solution, output $-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

Hint

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, D Olympic Bus.

Input Format

Output Format

Hint

Translated by ChatGPT 5