Phát biểu bài toán

Thành phố ByteLand là trung tâm công nghệ nổi tiếng, với mạng lưới giao thông bao gồm ~ N ~ nút giao thông (đánh số từ 1 đến ~ N ~) và ~ M ~ con đường hai chiều. Tượng đài "Người lập trình vô danh" nằm ở nút số 1. Các khách du lịch muốn di chuyển giữa các nút giao thông để tham quan.

Mỗi khách du lịch muốn đi từ nút ~ u_i ~ đến nút ~ v_i ~. Tính chi phí thấp nhất mà mỗi khách phải trả để di chuyển bằng taxi, biết rằng giá taxi là 1 BCoin cho mỗi đơn vị độ dài.

Dữ liệu vào

1. Dòng đầu tiên chứa ba số nguyên ~ N, M, P ~:

   • ~ N ~ (~1 \leq N \leq 50,000~): Số nút giao thông.
   • ~ M ~ (~N-1 \leq M \leq 100,000~): Số con đường.
   • ~ P ~ (~1 \leq P \leq 25,000~): Số khách du lịch.

2. ~ M ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ u_i, v_i, L_i ~:

   • ~ u_i, v_i ~: Hai nút giao thông được kết nối bởi con đường thứ ~ i ~.
   • ~ L_i ~ (~1 \leq L_i \leq 2000~): Độ dài của con đường.

3. ~ P ~ dòng tiếp theo, mỗi dòng chứa hai số ~ s_j, t_j ~:

   • ~ s_j ~: Nút xuất phát của khách du lịch thứ ~ j ~.
   • ~ t_j ~: Nút đích của khách du lịch thứ ~ j ~.

Dữ liệu ra

• In ~ P ~ dòng, mỗi dòng là chi phí thấp nhất mà khách thứ ~ j ~ phải trả.

Ví dụ minh hoạ

Input

6 7 3
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
2 4
5 1
3 6

Output

6
6
10

Giải thích:

• Chi phí đi từ nút 2 đến nút 4 là 6.
• Chi phí đi từ nút 5 đến nút 1 là 6.
• Chi phí đi từ nút 3 đến nút 6 là 10.