Cho đồ thị vô hướng liên thông gồm đỉnh và cạnh. Cạnh thứ nối đỉnh với đỉnh có độ dài . Cho truy vấn thuộc một trong hai loại:
- : In độ dài đường đi ngắn nhất từ đỉnh đến đỉnh ;
- : In đỉnh thứ trên đường đi ngắn nhất từ đến .
Yêu cầu: Với mỗi truy vấn, tìm kết quả tương ứng.
Dữ liệu vào:
- Dòng đầu chứa hai số ;
- dòng sau, dòng thứ chứa ba số nguyên ;
- dòng cuối, mỗi dòng chứa thông tin một truy vấn thuộc một trong hai loại ở trên.
Dữ liệu đảm bảo truy vấn loại tồn tại đáp số.
Dữ liệu ra:
- Tương ứng với mỗi truy vấn, ghi kết quả tìm được trên một hàng.
Ví dụ:
Dữ liệu vào:
6 2
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
1 4 6
2 4 6 4
Dữ liệu ra:
Giới hạn:
- Subtask tổng số điểm có ;
- Subtask tổng số điểm tiếp theo có và tất cả các truy vấn là loại ;
- Subtask tổng số điểm còn lại không có ràng buộc gì thêm.
