Khu vực bạn đang sống có ~n~ thành phố và chúng được nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối giữa ~2~ thành phố ~u_i~ và ~v_i~ và bạn cần thời gian ~t_i~ để đi hết con đường thứ ~i~.

Là một đặc vụ ngầm mới gia nhập tổ chức, bạn cải trang thành một shipper. Trong ~q~ ngày tiếp theo, ngoài các đơn hàng bình thường ra, mỗi ngày bạn cần phải vận chuyển một đơn hàng bí mật cho tổ chức. Ngày thứ ~i~ bạn cần vận chuyển đơn hàng bí mật này từ thành phố ~x_i~ đến thành phố ~y_i~.

Để thể hiện được là một đặc vụ chuyên nghiệp, bạn cần phải giao đơn hàng bí mật này trong thời gian ngắn nhất có thể. Trong ~q~ ngày tới, hãy tính xem ngày thứ ~i~ bạn cần mất bao nhiêu thời gian để hoàn thành nhiệm vụ.

Input

• Dòng đầu tiên gồm 3 số nguyên dương ~n~, ~m~ và ~q~.

• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm 3 số nguyên dương ~u_i~, ~v_i~ và ~t_i~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên dương ~x_i~ và ~y_i~.

Ràng buộc dữ liệu

• ~1 \leq n, q \leq 10^5~.

• ~n-1 \leq m \leq n+30~.

• ~1 \leq u_i, v_i, x_i, y_i \leq n~.

• ~1 \leq t_i \leq 2 \cdot 10^5~.

• Dữ liệu đảm bảo liên thông giữa ~n~ thành phố.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ chứa một số nguyên là thời gian giao hàng ngắn nhất trong ngày ~i~.

Scoring

Subtasks

Sample Input 1

5 6 3
1 2 5
1 3 2
2 3 1
2 4 8
3 4 9
4 5 2
1 5
5 2
3 5

Sample Output 1

13
10
11

Sample Input 2

5 5 3
1 2 5
2 3 5
3 4 4
4 5 1
5 1 2
1 3
2 5
2 4

Sample Output 2

7
7
8