Tối ưu

Thành phố Ngân là một trong những trung tâm đô thị phát triển bậc nhất, với mạng lưới giao thông hiện đại nhưng phức tạp. Hệ thống bao gồm \(n\) nút giao thông (tượng trưng cho các ngã tư, vòng xuyến, hay điểm giao giữa các tuyến đường) và \(m\) tuyến đường một chiều nối các nút này.

Tuy nhiên, dưới áp lực dân số tăng cao và sự phát triển kinh tế, chính quyền thành phố buộc phải đánh giá lại hệ thống hạ tầng và tìm giải pháp tối ưu hoá thời gian di chuyển trong nội đô. Việc này đòi hỏi các chuyên gia thuật toán, như bạn, tìm ra những cải tiến hiệu quả nhất với chi phí thấp nhất.

Mỗi tuyến đường trong thành phố là một đoạn một chiều cho phép đi từ nút $u_i$ đến nút $v_i$, và mất $t_i$ đơn vị thời gian để đi qua. Thành phố muốn tìm cách rút ngắn thời gian đi từ trung tâm hành chính (nút $1$) đến các khu vực khác (nút $s$) bằng cách **nâng cấp một tuyến đường bất kỳ**. Sau khi được nâng cấp, thời gian qua tuyến đó giảm còn đúng $t_0$.

**Lưu ý:** Chỉ được phép nâng cấp nhiều nhất một tuyến đường. Bạn không thể nâng cấp nhiều tuyến đường cùng lúc.

Input

• Dòng đầu gồm ba số nguyên \(n\), \(m\), \(q\) --- số nút, số tuyến đường, và số yêu cầu truy vấn \((1 \le n \le 2000,\ 1 \le m \le 10^4,\ 1 \le q \le 2 \cdot 10^6)\).
• \(m\) dòng tiếp theo: mỗi dòng gồm ba số nguyên \(u_i\), \(v_i\), \(t_i\) --- mô tả tuyến đường đi từ \(u_i\) đến \(v_i\) với thời gian gốc là \(t_i\) \((1 \le u_i, v_i \le n; u_i \ne v_i; 1 \le t_i \le 2000)\).
• \(q\) dòng tiếp theo: mỗi dòng gồm hai số nguyên \(s\) và \(t_0\) --- tương ứng là điểm đến và thời gian sau khi nâng cấp \((1 \le s \le n; 1 \le t_0 \le 2000)\).

Output

Ghi ra \(q\) dòng, dòng thứ \(j\) là thời gian ngắn nhất để đi từ nút \(1\) đến nút \(s\) của truy vấn thứ \(j\), khi được phép nâng cấp nhiều nhất một tuyến đường.

Nếu không thể đi từ nút $1$ đến nút $s$ (dù nâng cấp bất kỳ tuyến nào), in ra `-1`.

Example

4 4 3
1 2 6
2 4 10
1 3 16
3 4 4
3 14
4 14
4 11

14
16
15

Scoring

• Subtask 1 (30% số điểm): \(n \le 20\), \(q \le 200\).
• Subtask 2 (40% số điểm): \(n \le 200\), \(q \le 2000\).
• Subtask 3 (30% số điểm): \(n \le 2000\), \(q \le 2 \cdot 10^6\).