Đường Đi Ngắn Nhất II

Có $n$ thành phố và $m$ con đường hai chiều giữa chúng. Cho $q$ truy vấn, mỗi truy vấn yêu cầu tìm độ dài đường đi ngắn nhất giữa hai thành phố cho trước.

Dữ liệu vào

• Dòng 1: ba số nguyên $n$, $m$, $q$.
• $m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$, $b$, $c$ — con đường hai chiều giữa $a$ và $b$ với độ dài $c$.
• $q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$, $b$ — truy vấn khoảng cách ngắn nhất từ $a$ đến $b$.

Dữ liệu ra

Với mỗi truy vấn, in khoảng cách ngắn nhất, hoặc $-1$ nếu không tồn tại đường đi.

Ràng buộc

• $1\le n\le 500$
• $1\le m\le n^2$
• $1\le q\le {10}^5$
• $1\le c\le {10}^9$

Ví dụ