올림픽 버스

JOI 왕국에는 1번부터 N번까지 번호가 붙은 N개의 도시가 있다. 도시 사이를 잇는 M개의 버스 노선이 있고, 1번부터 M번까지 번호가 붙어 있다. i번째 버스 노선(1 ≤ i ≤ M)은 도시 Ui에서 도시 Vi로 운행하며 요금은 Ci엔이다. i번째 버스 노선(1 ≤ i ≤ M)에서는 도시 Ui가 아닌 다른 도시에서 승차할 수 없다. 또한 도시 Vi가 아닌 다른 도시에서 하차할 수 없다. 한 도시에서 다른 도시로 가는 버스 노선이 여러 개 있을 수 있다.

곧 JOI 왕국에서 올림픽이 열린다. K 대통령은 JOI 왕국의 교통부 장관이다. K 대통령은 기껏해야 하나의 버스 노선을 골라, 올림픽이 열리기 직전에 요금을 바꾸지 않고 방향을 반대로 바꾼다. 즉, i번째 버스 노선(1 ≤ i ≤ M)을 고르면 올림픽 기간 동안 그 노선은 도시 Ui에서 도시 Vi로 운행하지 않고, 대신 도시 Vi에서 도시 Ui로 운행한다. 방향을 바꾸는 비용은 Di엔이고, 이 비용은 K 대통령이 지불한다. 혼란을 피하기 위해 올림픽 기간 중에는 방향을 바꿀 수 없다.

K 대통령은 교통부 장관이므로 올림픽 기간 동안 버스 노선을 이용해 도시 1과 도시 N 사이를 왕복한다. 방향을 바꿀 버스 노선을 적절히 고르거나 고르지 않아서, 왕복 비용과 고른 버스 노선의 방향을 바꾸는 비용의 합을 최소로 만들고자 한다.

도시의 수와 버스 노선 정보가 주어질 때, 왕복 비용과 고른 버스 노선의 방향을 바꾸는 비용의 합의 최솟값을 계산하는 프로그램을 작성하라. 버스 노선을 골라서 도시 1과 도시 N 사이를 왕복하는 것이 불가능하면 -1을 출력한다.

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

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

왕복 비용과 고른 버스 노선의 방향을 바꾸는 비용의 합의 최솟값을 표준 출력에 쓴다. 도시 1과 도시 N 사이를 왕복하는 것이 불가능하면 -1을 쓴다.

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