DULICH1299 Chuyến du lịch

Đất nước Anpha có N thành phố và M con đường hai chiều nối giữa một số thành phố để đảm bảo hai thành phố bất kì luôn đến được với nhau thông qua các con đường. Giữa hai thành phố chỉ có tối đa một con đường và không có con đường từ một thành phố đến chính nó.

Tèo dự định đến nước Anpha để du lịch nên đã thiết lập một bản đồ gồm thời gian di chuyển qua các con đường và thời gian dừng lại tham quan mỗi thành phố. Tuy nhiên, vì thời gian có hạn, nên chuyến đi của Tèo sẽ xuất phát từ thành phố S, di chuyển đến thành phố T, chỉ dừng lại tham quan một thành phố có thời gian lớn nhất nằm trên tuyến đường đó. Tổng thời gian của chuyến đi bằng tổng thời gian đi qua các con đường cộng với thời gian tham quan thành phố.

Tèo hiện có K lựa chọn, mỗi lựa chọn là một truy vấn dạng S T. Với mỗi lựa chọn, hãy giúp Tèo tìm thời gian ít nhất để thực hiện chuyến đi từ thành phố S đến thành phố T.

Input

• Dòng đầu ghi 3 số N, M, K (1 ≤ N ≤ 250; 1 ≤ M ≤ 10⁴; 1 ≤ K ≤  10⁴)
• N dòng sau, dòng thứ i ghi số ngyên C_i là thời gian tham quan thành phố thứ i. (1 ≤ C_i ≤ 10⁵)
• M dòng sau, dòng thứ i ghi ba số nguyên A_i B_i L_i cho biết có con đường nối từ thành phố A_i đến thành phố B_i, có thời gian L_i (1 ≤ L_i ≤ 10⁵)
• K dòng cuối, dòng thứ i ghi hai số nguyên S_i T_i là lựa chọn thứ i.

Output: mỗi dòng ghi một số nguyên, dòng thứ i là câu trả lời của lựa chọn thứ i cho biết thời gian nhỏ nhất của chuyến đi đi từ thành phố S_i đến thành phố T_i

Input	Output	Giải thích
5 7 2 2 5 3 3 4 1 2 3 1 3 2 2 5 3 5 3 1 5 4 1 2 4 3 3 4 4 1 4 2 3	8 9	Lựa chọn 1: đường đi có thời gian ít nhất là 1 > 3 > 5 > 4 có tổng thời gian là: 2 + 1 + 1 + 4 = 8, tham quan thành phố 5 Lựa chọn 2: đường đi có thời gian ít nhất là 2 > 5 > 3 có tổng thời gian là 3 + 1 + 5 = 9, tham quan thành phố 2.