복수

Gigel은 양의 비용을 가진 무방향 그래프 $G$를 가지고 있으며, 이 그래프는 $N$개의 정점과 $M$개의 간선으로 이루어진다. 루마니아 국립 정보올림피아드에서 일이 꼬인 뒤, Gigel의 동생 Ninel이 Gigel의 간선을 모두 훔쳐 갔다. Gigel은 간선을 되찾고 싶지만, Ninel은 그에게 여러 도전 과제를 준다. 길이가 $L$인 무방향 간선 배열 $S$가 주어진다. 각 간선은 일반 비용과 거절 비용 $r$을 가진다. Gigel은 Ninel이 준 임무를 수행해야 한다. 임무는 $S$의 간선 부분 배열만 사용해서 정점 $u$에서 정점 $v$까지 가는 최소 비용을 구하는 것이다. 사용할 수 있는 간선은 인덱스 구간 $[a,b]$ ($a \le b$)로 정해지며, 이 구간이 Gigel이 쓸 수 있는 $S$의 간선 번호를 나타낸다.

Gigel은 정점 $x$에서 출발해 간선 $S_a, S_{a+1}, \dots, S_b$를 차례로 본다. 각 단계에서 그는 다음 둘 중 하나를 고른다. 현재 간선 $(x,y)$를 사용해 $x$에 있으면 $y$로 이동하고, $y$에 있으면 $x$로 이동한다. 이때 이동 비용에 간선의 비용이 더해진다. 아니면 현재 간선을 거절하고 현재 정점에 머문다. 이때 이동 비용에 간선의 거절 비용이 더해진다.

$N$, 배열 $S$, 그리고 $Q$개의 임무가 주어진다. $S$의 각 원소는 비용 $c$와 거절 비용 $r$을 가진 간선 $(x,y)$를 나타내는 $\langle x,y,c,r \rangle$ 형태다. 각 임무는 $\langle u,v,a,b \rangle$ 형태이며, Gigel은 $u$에서 출발해 $v$에 도달해야 하고, 인덱스가 $a$부터 $b$ 사이인 간선만 쓸 수 있다. 각 임무의 최소 비용을 구하라. $v$에 도달할 수 없으면 $-1$을 출력한다.

첫 줄에 세 정수 $N$, $L$, $Q$가 주어진다. 다음 $L$개의 줄에는 $S$의 간선을 나타내는 네 정수 $x$, $y$, $c$, $r$이 주어진다. 그다음 $Q$개의 줄에는 임무를 나타내는 네 정수 $u$, $v$, $a$, $b$가 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 임무의 답을 출력한다.

$2 \le N \le 30$, $1 \le L \le 3 \times 10^4$, $1 \le Q \le 3 \times 10^5$, $0 \le c, r \le 10^4$, $1 \le x, y, u, v \le N$.