Kaka와 Bebe

"Kaka Is You"라는 퍼즐 게임이 인디 게이머들 사이에서 조용히 인기를 끌고 있다. 현식이도 예외가 아니었다. 현식이는 끙끙대며 밤새 퍼즐을 풀다가 잠이 들었다. 눈을 떴더니 눈앞에 "Kaka Is You"의 등장동물 Kaka와 Bebe가 잔뜩 보이기 시작했다. 현식이는 생각했다.

'아니, 이건 꿈이야! 내가 꿈속에서까지 Kaka와 Bebe를 봐야 해?'

그런데 저 멀리 탈출구가 보인다. 분명 저 탈출구로 나가면 꿈에서 깨어날 수 있을 것이다.

현식이의 현재 상황은 다음과 같다. 정점 $N$개로 이루어진 그래프가 주어진다. 각 정점에는 0번부터 $N-1$번까지 번호가 붙어 있고, 현식이는 정점 0번에, 탈출구는 정점 $N-1$번에 있다. 간선은 모두 양방향이며 총 $M$개가 있다. 각 간선에도 0번부터 $M-1$번까지 번호가 붙어 있고, $i$번 간선 위에는 Kaka가 $c_i$마리, Bebe가 $d_i$마리가 있다. $c_i$와 $d_i$는 모두 1 이상 1,000 이하이다. 즉, 모든 간선마다 Kaka와 Bebe가 한 마리씩은 있다. 으악!

현식이는 다음 조건을 만족하는 0번 정점에서 $N-1$번 정점까지의 경로를 찾아 탈출구로 나가야 한다.

1. 경로에 있는 Kaka의 총 마릿수와 Bebe의 총 마릿수는 각각 1,000을 넘어서는 안 된다.
2. 해당 경로의 스트레스는 (Kaka의 총 마릿수)×(Bebe의 총 마릿수)로 정의된다. 1번을 만족하는 경로가 여러 개라면 그중 스트레스가 가장 적은 경로를 선택한다.

위 그림은 첫 번째 예시를 나타낸 것이다. 각 간선의 $(a, b)$는 $(c_i, d_i)$를 나타낸다. 보다시피 0번과 3번을 잇는 간선을 지나면 어떤 형태로든 Kaka의 총 마릿수가 1,000을 넘어가므로 지나갈 수 없다. 가능한 경로 중 스트레스가 가장 적은 경로는 0번, 1번, 3번, 4번 순서로 지나가는 경로이고, 스트레스 값은 $(1+2+1)\times(1+2+7)=40$이다.

위 그림은 두 번째 예시를 나타낸 것이다. 두 번째 예시에서는 어떤 경로로 가도 Kaka나 Bebe의 마릿수가 1,000을 넘어가므로 답이 존재하지 않는다. 따라서 -1을 출력한다.

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백을 사이에 두고 주어진다. (2 ≤ $N$ ≤ 1,000, 1 ≤ $M$ ≤ 10,000)

두 번째 줄부터 $M+1$번째 줄까지, $(1+i)$번째 줄에 $i$번 간선의 정보 $a_i$, $b_i$, $c_i$, $d_i$가 공백을 사이에 두고 주어진다. 이는 $a_i$번과 $b_i$번 정점을 잇는 간선이 존재하며, 그 위에 Kaka가 $c_i$마리, Bebe가 $d_i$마리 있다는 뜻이다. (0 ≤ $a_i, b_i < N$, 1 ≤ $c_i, d_i$ ≤ 20,000)

두 정점을 잇는 간선은 두 개 이상 존재하지 않는다.

조건을 만족하는 경로의 스트레스 값 ((Kaka의 총 마릿수)×(Bebe의 총 마릿수))을 출력한다.

그러한 경로가 존재하지 않으면 -1을 출력한다.

첫 번째 예시에서 0번과 3번을 잇는 간선을 지나면 어떤 형태로든 Kaka의 총 마릿수가 1,000을 넘어가므로 지나갈 수 없다. 가능한 경로 중 스트레스가 가장 적은 경로는 0번, 1번, 3번, 4번 순서로 지나가는 경로이고, 스트레스 값은 $(1+2+1)\times(1+2+7)=40$이다.

두 번째 예시에서는 어떤 경로로 가도 Kaka나 Bebe의 마릿수가 1,000을 넘어가므로 답이 존재하지 않는다. 따라서 -1을 출력한다.