Một mạng máy tính bao gồm \(n\) máy tính được đánh số từ 1 đến \(n\) và \(n - 1\) dây cáp mạng, mỗi dây nối giữa hai máy tính bất kỳ. Không có cáp mạng nối một máy với chính nó. Các máy tính có thể truyền dữ liệu trực tiếp cho nhau thông qua các cáp mạng hoặc thông qua các máy trung gian. Mỗi cáp mạng có một tốc độ truyền tin \(w_{i}\) khác nhau.

Mạng máy tính này đang đối mặt với nguy cơ bị tấn công từ hacker. Khi một máy tính \(u\) bị tấn công, nó sẽ bị tê liệt và không thể nhận hay gửi dữ liệu. Vì dữ liệu lưu trữ trên các máy tính là vô cùng quan trọng, nhóm quản trị đã lên kế hoạch sao lưu toàn bộ dữ liệu từ máy tính \(u\) sang máy tính \(v\) để đề phòng việc máy tính \(u\) bị tấn công. Nhóm quản trị viên muốn biết trên đường truyền từ máy \(u\) đến máy \(v\), dây cáp mạng có tốc độ nhỏ nhất là bao nhiêu? Công việc này rất gấp, nên họ để sót một lỗi nhỏ: \(u\) có thể sao lưu sang chính nó.

Yêu cầu: hãy xử lý \(q\) truy vấn thuộc một trong 2 loại sau

+ \(1\ u\ v\): tìm tốc độ truyền tin nhỏ nhất của các cáp mạng trên đường truyền từ máy \(u\) đến máy \(v\). Nếu không thể truyền dữ liệu từ \(u\) đến \(v\), in ra -1.

+ \(2\ u:\) máy tính \(u\) bị tê liệt hoàn toàn.

Dữ liệu vào:

+ Dòng thứ nhất chứa hai số nguyên \(n,\ q\ (n,\ q \leq 10^{5})\) lần lượt là số máy tính trong mạng và số truy vấn cần thực hiện;

+ \(n - 1\) dòng tiếp theo, dòng t hứ \(i\) chứa ba số nguyên \(u_{i},\ v_{i},\ w_{i}\ (u_{i},\ v_{i} \leq n,\ w_{i} \leq 10^{6})\) mô tả một cáp mạng nối hai máy tính \(u_{i},\ v_{i}\) có tốc độ truyền dữ liệu là \(w_{i}.\)

+ \(q\) dòng tiếp theo, dòng thứ \(i\) mô tả truy vấn thứ \(i\) thuộc một trong hai loại

• \(1\ u\ v\ (u,\ v \leq n)\);

• \(2\ u\ (u \leq n)\).

Kết quả: Gồm một số dòng tương ứng là các câu trả lời cho thao tác loại 1.

Ví dụ

Ràng buộc:

• Subtask 1: 20% số test đầu tiên có \(n,\ q \leq 1000;\)

• Subtask 2: 20% số test tiếp theo chỉ có truy vấn loại 1 và \(n,\ q \leq 10^{5};\)

• Subtask 3: 20% số test tiếp theo đảm bảo tất cả các truy vấn loại 2 xảy ra trước tất cả các truy vấn loại 1 và \(n,\ q \leq 10^{5};\)

• Subtask 4: 20% số test tiếp theo đảm bảo một máy không có quá 2 cáp nối đến máy khác;

• Subtask 5: 20% số test còn lại không có ràng buộc gì.