Interstellar Train

In the year 2992, robots have taken most jobs. Many people now have plenty of free time, and your family has decided to travel between the stars!

There are $N$ reachable planets, numbered from $0$ to $N-1$, and $M$ interstellar train routes. Route $i$ ($0 \le i < M$) leaves planet $X[i]$ at time $A[i]$, arrives at planet $Y[i]$ at time $B[i]$, and costs $C[i]$. Trains are the only way to travel between planets. You can only get off a train at its destination planet, and you must board the next train from that same planet. Transfers take no time. Formally, a sequence of trains $q[0], q[1], \dots, q[P]$ is valid if and only if for every $1 \le k \le P$, $Y[q[k-1]] = X[q[k]]$ and $B[q[k-1]] \le A[q[k]]$.

Interstellar travel takes a long time, so meals add a significant cost on top of the train fares. Fortunately, interstellar trains provide unlimited food for free. If you take route $i$, you can eat any number of meals at no cost at any time between $A[i]$ and $B[i]$ (inclusive). While your family waits for the next train on planet $i$, however, each meal costs $T[i]$.

Your family must eat $W$ meals. The $i$-th meal ($0 \le i < W$) can be eaten instantaneously at any time between $L[i]$ and $R[i]$ (inclusive).

At time $0$, your family is on planet $0$. Find the minimum total cost to reach planet $N-1$. If it is impossible to reach planet $N-1$, the answer is $-1$.

• $2 \le N \le 10^5$.
• $0 \le M, W \le 10^5$.
• $0 \le X[i], Y[i] < N$, $X[i] \ne Y[i]$.
• $1 \le A[i] < B[i] \le 10^9$.
• $1 \le T[i], C[i] \le 10^9$.
• $1 \le L[i] \le R[i] \le 10^9$.