Problem Description

In the country of JOI, there are $ N $ cities numbered from $ 1 $ to $ N $. Additionally, there are $ M $ bus routes connecting cities in one direction, numbered from $ 1 $ to $ M $. Bus route $ i $ ($1 \leq i \leq M$) operates from city $ U_i $ to city $ V_i $ with a fare of $ C_i $ yen. On bus route $ i $ ($1 \leq i \leq M$), you can only board at city $ U_i $ and alight at city $ V_i $. There may be multiple bus routes operating from one city to another.

The Olympic Games are about to be held in JOI. K, the transportation minister of JOI, has decided to select at most one bus route and reverse its direction without changing the fare during the Olympic period. That is, if bus route $ i $ ($1 \leq i \leq M$) is chosen, during the Olympic period, it will operate from city $ V_i $ to city $ U_i $ instead of from city $ U_i $ to city $ V_i $. However, reversing the direction of bus route $ i $ costs $ D_i $ yen, which will be covered by K's pocket money. Also, to avoid confusion, bus routes cannot be reversed during the middle of the Olympic period.

K, the transportation minister, plans to travel back and forth between city $ 1 $ and city $ N $ using bus routes during the Olympic period. By carefully selecting the bus route to reverse its direction, K wants to minimize the sum of the total round-trip fare between city $ 1 $ and city $ N $ and the cost of reversing the direction of the bus route.

Given the number of cities and the information about the bus routes, create a program that calculates the minimum sum of the total round-trip fare between city $ 1 $ and city $ N $ and the cost of reversing the direction of the bus route. If it is impossible to travel back and forth between city $ 1 $ and city $ N $ regardless of which bus route is chosen, output $ -1 $ instead.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ N $ $ M $ $ U_1 $ $ V_1 $ $ C_1 $ $ D_1 $ $\vdots$ $ U_M $ $ V_M $ $ C_M $ $ D_M $

Output Format

Output the minimum sum of the total round-trip fare between city $ 1 $ and city $ N $ and the cost of reversing the direction of the bus route in one line to the standard output. If it is impossible to travel back and forth between city $ 1 $ and city $ N $ regardless of which bus route is chosen, output $ -1 $ instead.

Sample Input and Output

Sample Input #1

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

Sample Output #1

10

Sample Input #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

Sample Output #2

10

Sample Input #3

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

Sample Output #3

2

Sample Input #4

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

Sample Output #4

12

Sample Input #5

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

Sample Output #5

-1

Notes/Hints

Constraints

• $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$).

Subtasks

1. ($ 5 $ points) $M \leq 1,000$.
2. ($ 11 $ points) $ M $ is even, $ U_{2i - 1} = U_{2i} $, $ V_{2i - 1} = V_{2i} $, $ C_{2i - 1} = C_{2i} $ ($1 \leq i \leq \frac{M}{2}$).
3. ($ 21 $ points) $ C_i = 0 $ ($1 \leq i \leq M$).
4. ($ 63 $ points) No additional constraints.

Sample Explanation 1

By reversing the direction of bus route $ 2 $ at a cost of $ 1 $, the fare for traveling from city $ 1 $ to city $ 4 $ is minimized to $ 6 $, and the fare for traveling from city $ 4 $ to city $ 1 $ is minimized to $ 3 $. The sum of the total round-trip fare and the cost of reversing the direction is $ 10 $. Since it is not possible to reduce this sum below $ 10 $, output $ 10 $.

Sample Explanation 2

This input/output example satisfies the constraints of subtask $ 2 $.

Sample Explanation 3

This input/output example satisfies the constraints of subtask $ 3 $.

Sample Explanation 4

It is not necessary to reverse the direction of any bus route.

Sample Explanation 5

In this input example, there are two bus routes operating from city $ 4 $ to city $ 3 $.

见题面 Input 部分

见题面 Output 部分