Olympic Bus

Time limit2sMemory limit512 MB

Summary
Choose at most one directed bus edge to reverse, paying its reversal cost, so that a round trip from city 1 to N and back exists, minimizing total fare plus reversal cost.
Level

Hard8 of 10

Topics
Graph, Shortest path, Dynamic programming, Greedy
Solved
No attempts yet

Problem

There are N cities in JOI Kingdom, numbered from 1 to N. There are M bus lines connecting cities, numbered from 1 to M. The i-th bus line (1 ≤ i ≤ M) runs from the city Ui to the city Vi, and its fare is Ci yen. On the i-th bus line (1 ≤ i ≤ M), a passenger cannot get on the bus in a city other than the city Ui. Also, a passenger cannot get off the bus in a city other than the city Vi. There may be more than one bus line from a city to another city.

The Olympic Games will be held in JOI Kingdom soon. President K is the Minister of Transport of JOI Kingdom. President K will choose at most one bus line, and invert its direction without changing its fare just before the Olympic Games. Namely, if he chooses the i-th bus line (1 ≤ i ≤ M), it will not run from the city Ui to the city Vi during the Olympic Games; instead, it will run from the city Vi to the city Ui. The cost to invert the direction is Di yen, and it will be paid by President K. In order to avoid confusion, it is not allowed to invert the direction during the Olympic Games.

Since President K is the Minister of Transport, during the Olympic Games, he will make a round trip between the city 1 and the city N using the bus lines. By choosing (or not choosing) a bus line to be inverted appropriately, he wants to minimize the sum of the cost of the round trip and the cost to invert the chosen bus line.

Write a program which, given the number of cities and information of the bus lines, calculates the minimum sum of the cost of the round trip and the cost to invert the chosen bus line. If it is not possible to make a round trip between the city 1 and the city N by choosing a bus line to be inverted, output −1 instead.

Input

Read the following data from the standard input. Given values are all integers.

N M
U1 V1 C1 D1
.
.
.
UM VM CM DM

Output

Write the minimum sum of the cost of the round trip and the cost to invert the chosen bus line to the standard output. If it is not possible to make a round trip between the city 1 and the city N, write −1 instead.

Constraints

  • 2 ≤ N ≤ 200.
  • 1 ≤ M ≤ 50 000.
  • 1 ≤ Ui ≤ N (1 ≤ i ≤ M).
  • 1 ≤ Vi ≤ N (1 ≤ i ≤ M).
  • Ui, Vi (1 ≤ i ≤ M).
  • 0 ≤ Ci ≤ 1 000 000 (1 ≤ i ≤ M).
  • 0 ≤ Di ≤ 1 000 000 000 (1 ≤ i ≤ M).

Examples5

  1. Example 1

    Input
    4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5
    Expected output
    10

  2. Example 2

    Input
    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
    Expected output
    10

  3. Example 3

    Input
    4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1
    Expected output
    2

  4. Example 4

    Input
    4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5
    Expected output
    12

  5. Example 5

    Input
    4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5
    Expected output
    -1