Tắc đường

VP là một thành phố vô cùng đặc biệt. Ngoài vẻ đẹp tự nhiên thu hút khách du lịch, hệ thống giao thông cũng vô cùng đặc biệt. Thành phố được kết nối bởi $n$ điểm với $m$ con đường phục vụ di chuyển đảm bảo liên thông toàn thành phố. Con đường thứ $i$ kết nối hai chiều giữa hai điểm $u_i$ và $v_i$ với thời gian di chuyển là $p_i$. Tuy nhiên, trong trường hợp xấu xảy ra tắc đường, để đi hết con đường này cần thời gian là $q_i$.

Hà là một quản lý trong một công ty vận tải, Hà đang thiết kế lộ trình cố định cho tuyến xe phục vụ đưa đón khách du lịch bắt đầu từ $s$, di chuyển qua một số con đường và kết thúc tại điểm $t$. Giả thiết trong trường hợp xấu nhất, chỉ có một con đường trên tuyến đường di chuyển đó gặp sự cố tắc đường. Nói cách khác, nếu con đường $i$ trên lộ trình bị tắc thì thời gian di chuyển là tổng thời gian $p$ của các con đường trên lộ trình, trong đó $p_i$ được thay bằng $q_i$; thời gian trong trường hợp xấu nhất là giá trị lớn nhất trong các khả năng đó. Nếu $s=t$ thì xe không cần đi con đường nào và thời gian là $0$.

Yêu cầu: Cho $k$ truy vấn, mỗi truy vấn gồm $2$ số $s,t$ ($1\le s,t\le n$). Với mỗi truy vấn, hãy giúp Hà lựa chọn một lộ trình cố định sao cho trong trường hợp xấu nhất, tổng thời gian di chuyển của xe là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n,m,k$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $4$ số nguyên dương $u_i,v_i,p_i,q_i$ ($u_i,v_i\le n$; $p_i<q_i\le {10}^5$, $\forall i=1,2,\dots ,m$).
• $k$ dòng cuối cùng, dòng thứ $j$ chứa hai số nguyên dương $s,t$ xác định thông tin trong truy vấn thứ $j$ ($s,t\le n$, $\forall j=1,2,\dots ,k$).

Dữ liệu ra

In ra $k$ dòng, dòng thứ $j$ đưa ra câu trả lời cho truy vấn thứ $j$ là tổng thời gian di chuyển theo tuyến đường Hà lựa chọn trong trường hợp xấu nhất.

Ràng buộc

• $2\le n\le 1000$, $1\le m\le 5000$, $1\le k\le 10$.
• $1\le u_i,v_i\le n$, $u_i\ne v_i$; có thể có nhiều con đường nối cùng một cặp điểm; từ một điểm bất kỳ có thể đi tới mọi điểm khác.
• $1\le p_i<q_i\le {10}^5$.
• $1\le s,t\le n$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($20\%$ số test): $n\le 10$, $m\le 20$, $k=1$.
• Subtask 2 ($20\%$ số test): $n\le 100$, $m\le 1000$, $k\le 10$ và $q_1-p_1=q_2-p_2=\cdots =q_m-p_m$.
• Subtask 3 ($30\%$ số test): $n\le 300$, $m\le 1000$, $k\le 10$.
• Subtask 4 ($30\%$ số test): $n\le 1000$, $m\le 5000$, $k\le 10$.

Ví dụ