Cho đồ thị gồm ~ n ~ đỉnh và ~ m ~ cung có hướng. Hãy trả lời ~ q ~ câu hỏi dạng ~ s, t ~ cho biết độ dài đường đi ngắn nhất từ đỉnh ~ s ~ đến đỉnh ~ t ~?

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương ~ n, m ~ lần lượt là số đỉnh và số cung của đồ thị
• ~ m ~ dòng tiếp theo mỗi dòng gồm 3 số ~ u, v, c ~ cho biết một cung nối từ đỉnh ~ u ~ đến đỉnh ~ v ~ có độ dài ~ c ~
• Dòng tiếp theo ghi số nguyên ~ q ~ cho biết số lượng câu hỏi
• ~ q ~ dòng tiếp theo mỗi dòng chứa 2 số ~ s, t ~ cho biết thông tin về một câu hỏi.

Kết quả

Với mỗi câu hỏi trong Input, ghi ra kết quả trên 1 dòng. Nếu không có đường đi từ ~ s ~ đến ~ t ~ thì câu trả lời tương ứng là ~ -1 ~.

Ràng buộc

• ~ 2 ≤ n ≤ 400 ~
• ~ 1 ≤ q ≤ 10^5 ~
• ~ 1 ≤ s, t, u, v ≤ n ~
• ~ 1 ≤ c ≤ 350 ~

Ví dụ:

Input 1

4 5
1 2 5
1 4 24
2 4 6
3 4 4
3 2 7
3
1 2
3 1
1 4 

Output 1

```5 -1 11

```