Trung tâm dữ liệu

Giang hiện đang là kiến trúc sư trưởng cho tập đoàn viễn thông đa quốc gia G-Network. Hệ thống mạng lưới của tập đoàn bao gồm \(n\) trạm trung chuyển được đánh số từ \(1\) đến \(n\). Để tối ưu hóa chi phí vận hành, các trạm này được kết nối với nhau bởi \(n-1\) tuyến cáp quang hai chiều, sao cho giữa hai trạm bất kỳ luôn tồn tại một đường đi duy nhất. Mỗi tuyến cáp kết nối giữa trạm \(u\) và trạm \(v\) có độ dài vật lý là \(w\).

Trong chiến lược mở rộng thị trường, tập đoàn sẽ kích hoạt các trạm phát sóng tại các vị trí chiến lược. Giả sử tại một thời điểm, có một tập hợp \(S\) các trạm được chọn làm trạm phát sóng đặc biệt. Để quản lý dữ liệu từ các trạm này, tập đoàn cần thiết lập một Trung tâm điều hành G.

Vị trí đặt trung tâm G có thể là bất kỳ trạm nào trong số \(n\) trạm của mạng lưới. Để giảm thiểu độ trễ tín hiệu, Giang định nghĩa giá trị G là tổng khoảng cách ngắn nhất từ trung tâm G đến tất cả các trạm phát sóng đặc biệt trong tập \(S\). Trạm được chọn làm trung tâm G phải là trạm có tổng khoảng cách này là nhỏ nhất. (Lưu ý: Có thể có nhiều trạm thỏa mãn điều kiện làm trung tâm G, nhưng giá trị G là duy nhất).

Giang đưa ra \(q\) kế hoạch mở rộng khác nhau. Trong mỗi kế hoạch, anh cung cấp một danh sách gồm \(m\) trạm dự kiến sẽ được kích hoạt theo thứ tự \(a_1, a_2, \dots, a_m\). Đối với mỗi kế hoạch, Giang yêu cầu bạn thực hiện các báo cáo phân tích sau:
Với mỗi số nguyên \(x\) từ \(1\) đến \(m\), hãy tính giá trị G tại thời điểm tập trạm phát sóng đặc biệt mới chỉ gồm \(x\) trạm đầu tiên trong danh sách kích hoạt: \(S = \{a_1, a_2, \dots, a_x\}\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \leq n, q \leq 2 \times 10^{5}\)) --- số lượng trạm và số lượng kế hoạch.
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(w\) (\(1 \leq u, v \leq n, 1 \leq w \leq 10^{6}\)) mô tả một tuyến cáp quang nối trạm \(u\) và \(v\) với độ dài \(w\).

• \(q\) dòng tiếp theo, mỗi dòng mô tả một kế hoạch:

• Số đầu tiên là \(m\) (\(1 \leq m \leq n\)) --- số lượng trạm dự kiến kích hoạt.

• Tiếp theo là \(m\) số nguyên phân biệt \(a_1, a_2, \dots, a_m\) (\(1 \le a_i \le n\)) theo đúng thứ tự kích hoạt.

• Tổng giá trị \(m\) trong tất cả các truy vấn không vượt quá \(6 \times 10^{5}\).

Output

• Với mỗi kế hoạch (truy vấn), in ra \(m\) số nguyên trên một dòng, số thứ \(x\) là giá trị G tương ứng với tập \(x\) trạm phát sóng đầu tiên.

Example

10 2
3 5 2
5 6 2
6 7 2
6 8 2
8 9 1
2 4 1
4 10 2
3 4 1
1 3 2
5 1 2 3 4 5
4 4 1 5 2

0 4 4 5 7 
0 3 5 7 

Scoring

• Subtask 1 (17%): \(n \leq 5000\) và tổng \(m \leq 5000\).
• Subtask 2 (19%): Các trạm được nối với nhau thành một đường thẳng (\(1-2-3-\dots-n\)).
• Subtask 3 (20%): Mỗi kế hoạch luôn có đúng \(m = 3\) trạm.
• Subtask 4 (21%): Tất cả các tuyến cáp đều có cùng độ dài \(w = 1\).
• Subtask 5 (23%): Không có ràng buộc gì thêm.