Cho một đồ thị vô hướng, có trọng số với thành phố và con đường. Bạn cũng nhận được truy vấn. Đối với mỗi truy vấn, bạn cần tìm độ dài của tuyến đường ngắn nhất giữa hai thành phố cho trước.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên : số thành phố, số con đường, và số truy vấn.
dòng tiếp theo, mỗi dòng chứa ba số nguyên : một con đường từ đến với chiều dài . Tất cả các con đường đều là hai chiều.
dòng tiếp theo, mỗi dòng chứa hai số nguyên và : hai thành phố trong một truy vấn.
Kết quả: Đối với mỗi truy vấn, in ra độ dài của tuyến đường ngắn nhất. Nếu không có đường đi, in -1.
