고속도로 통행료

JOI 왕국은 $N$개의 도시로 이루어져 있으며, 도시에는 $1$번부터 $N$번까지 번호가 붙어 있다. JOI 왕국에는 도시를 잇는 일방통행 고속도로가 $M$개 있으며, 고속도로에는 $1$번부터 $M$번까지 번호가 붙어 있다. 고속도로 $i$($1 \le i \le M$)를 지나면 도시 $A_i$에서 도시 $B_i$로 이동하며, 통행에 걸리는 시간은 $L_i$이다.

고속도로를 지날 때마다 통행료가 든다. 고속도로 $i$의 통행료는 최소 $C_i$이지만, JOI 왕국의 노동자는 모두 초과 근무를 싫어하기 때문에 기준 시각 $0$에서 멀리 떨어질수록 통행료가 늘어난다. 구체적으로, 도시 $A_i$를 시각 $t$에 출발해 고속도로 $i$를 지나면 통행료는 상수 $K$에 대해 $C_i + K \times |t|$이다. 여기서 $|t|$는 $t$의 절댓값이다.

도시 $1$에 사는 당신은 친구가 있는 도시 $N$으로 놀러 가려고 한다. 고속도로만 이용해서 도시 $1$에서 도시 $N$까지 이동하고 싶다. 먼저 이것이 가능한지 확인하고, 가능하다면 통행료 총합의 최솟값을 구하려 한다. 이동 경로와 각 도시를 출발하는 시각은 자유롭게 정할 수 있다. 특히 도시 $1$을 음수 시각에 출발해도 되고, 고속도로를 타지 않고 어떤 도시에 머물러 있어도 된다.

고속도로 정보와 상수 $K$가 주어졌을 때, 고속도로를 통해 도시 $1$에서 도시 $N$까지 이동할 수 있는지 판정하고, 가능하다면 통행료 총합의 최솟값을 출력하는 프로그램을 작성하라.

입력은 다음 형식으로 주어진다.

N M K
A_1 B_1 L_1 C_1
A_2 B_2 L_2 C_2
⋮
A_M B_M L_M C_M

고속도로를 통해 도시 $1$에서 도시 $N$까지 이동할 수 없으면 $-1$을 출력한다. 이동할 수 있다면 통행료 총합의 최솟값을 정수로 한 줄에 출력한다.

• $2 \le N \le 4\,000$
• $1 \le M \le 8\,000$
• $0 \le K \le 100\,000$
• $1 \le A_i \le N$ ($1 \le i \le M$)
• $1 \le B_i \le N$ ($1 \le i \le M$)
• $A_i \ne B_i$ ($1 \le i \le M$)
• $1 \le L_i \le 1\,000\,000$ ($1 \le i \le M$)
• $0 \le C_i \le 10^9$ ($1 \le i \le M$)
• 입력되는 모든 값은 정수이다.