18434번 - Olympic Bus 서브태스크다국어

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 U_i to the city V_i, and its fare is C_i yen. On the i-th bus line (1 ≤ i ≤ M), a passenger cannot get on the bus in a city other than the city U_i. Also, a passenger cannot get off the bus in a city other than the city V_i. 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 U_i to the city V_i during the Olympic Games; instead, it will run from the city V_i to the city U_i. The cost to invert the direction is D_i 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 ≤ U_i ≤ N (1 ≤ i ≤ M).
• 1 ≤ V_i ≤ N (1 ≤ i ≤ M).
• U_i, V_i (1 ≤ i ≤ M).
• 0 ≤ C_i ≤ 1 000 000 (1 ≤ i ≤ M).
• 0 ≤ D_i ≤ 1 000 000 000 (1 ≤ i ≤ M).