Problem Description

Given a directed graph with \( N \) vertices and \( M \) edges, each edge goes from \( U_i \) to \( V_i \) with a cost of \( C_i \).

The vertices are numbered from 1 to \( N \).

You can reverse an edge, changing it from \( U_i \) to \( V_i \) to \( V_i \) to \( U_i \), which incurs a cost of \( D_i \).

You need to travel from vertex 1 to vertex \( N \), and then back from vertex \( N \) to vertex 1. Determine the minimum total cost achievable by reversing at most one edge, or not reversing any, to complete the journey.

Input Format

The first line contains two integers \( N \) and \( M \), representing the number of vertices and edges, respectively.

The next \( M \) lines each contain four integers \( U_i \), \( V_i \), \( C_i \), and \( D_i \), representing an edge.

Output Format

Output a single integer representing the minimum total cost. If it is not possible to complete the journey, output \(-1\).

Sample Input and Output

Input Sample #1

4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5

Output Sample #1

10

Input Sample #2

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

Output Sample #2

10

Input Sample #3

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1

Output Sample #3

2

Input Sample #4

4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5

Output Sample #4

12

Input Sample #5

4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5

Output Sample #5

-1

Notes

Sample 1 Explanation

The optimal solution is to reverse the second edge, with a total cost of:

• Reversal cost \( 1 \).
• Shortest path from vertex 1 to \( N \) and back \( 1 \to 2 \to 4 \to 3 \to 1 \), with a cost of \( 4 + 2 + 1 + 2 = 9 \).

Sample 4 Explanation

It is not necessarily required to reverse any edge.

Sample 5 Explanation

There are two edges from vertex 4 to vertex 3.

Data Constraints

This problem uses subtask testing.

• 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 data:

• \( 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 部分

见题面 Output 部分