G. NCODERS - Tượng đài

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Thành phố ByteLand là một trung tâm tin học nổi tiếng trên thế giới. Đây cũng là nơi sinh sống và lập nghiệp của rất nhiều lập trình viên từ các nước khác nhau.

Mới đây, ở ByteLand đã xây dựng tượng đài "Người lập trình vô danh" để ghi nhận công lao của rất nhiều lập trình viên tuy không nổi tiếng nhưng lại cung cấp rất nhiều chương trình nhỏ tiện ích và miễn phí trên mạng internet. Đây cũng là một công trình kiến trúc đẹp và được thế giới xếp vào 1 trong 7 kỳ quan hiện đại.

Với mục đích giới thiệu kỳ quan này đến với mọi khách du lịch khi đến ByteLand, chính quyền thành phố ban hành qui định Tất cả các xe taxi khi chở khách du lịch đều phải đi qua tượng đài Người lập trình vô danh trên mỗi hành trình chở khách.

Mạng lưới giao thông của ByteLand bao gồm N nút giao thông (đánh số từ 1,2,\ldots,N) được nối với nhau bởi M con đường hai chiều. Mỗi con đường nối trực tiếp giữa hai nút giao thông nào đó. Có thể có nhiều con đường trực tiếp nối hai nút giao thông. Mỗi một con đường có một độ dài xác định. Tượng đài Người lập trình vô danh được xây dựng ở nút số 1 .

P khách du lịch, người khách thứ i có nhu cầu di chuyển từ nút giao thông u_i đến nút giao thông v_i bằng taxi. Hãy tính xem mỗi người phải trả ít nhất là bao nhiêu BCoin (đơn vị tiền tệ ở ByteLand) biết rằng giá taxi thống nhất là 1 BCoin cho 1 đơn vị độ dài.

Dữ liệu:

  • Dòng đầu tiên ghi ba số nguyên N,M,P\ (1≤P≤25000, 2\times P≤N≤50000, N-1≤M≤100000) ;
  • M dòng tiếp theo, dòng thứ i ghi ba số nguyên u_i, v_i, L_i thể hiện có một con đường hai chiều nối hai nút giao thông u_i v_i có độ dài L_i\ (1≤u_i, v_i≤N, 1≤L_i≤2000) ;
  • P dòng cuối cùng, dòng thứ j ghi hai số nguyên s_j t_j thể hiện rằng người khách du lịch thứ i muốn đi từ nút giao thông s_j đến nút giao thông t_j .

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu trống.

Kết quả:

  • Ghi ra P dòng, dòng thứ i ghi số nguyên T_i là số tiền ít nhất mà người du lịch thứ i phải trả cho chuyến taxi của mình.

Ví dụ:

Dữ liệu:

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

Kết quả:

6
6
10