시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 19 7 6 50.000%

문제

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 lines 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.

입력

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

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

출력

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.

제한

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

예제 입력 1

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

예제 출력 1

10

Assume that President K will invert the direction of the 2nd bus line; its cost is 1 yen. Then, the minimum cost to travel from the city 1 to the city 4 will be 6 yen, and the minimum cost to travel from the city 4 to the city 1 will be 3 yen. Thus, the sum of the cost of the round trip between the city 1 and the city 4 and the cost to invert the chosen bus line will be 10 yen.

Since the sum of the cost of the round trip between the city 1 and the city 4 and the cost to invert the chosen bus line cannot be cheaper than 10 yen, output 10.

예제 입력 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

예제 출력 2

10

예제 입력 3

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

예제 출력 3

2

예제 입력 4

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

예제 출력 4

12

It is not necessary to invert the direction of a bus line.

예제 입력 5

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

예제 출력 5

-1

In this sample input, there are 2 bus lines from the city 4 to the city 3.