Giang là một nhà khoa học tài ba, chuyên nghiên cứu về đồ thị, đặc biệt là cây.

Hôm nay Giang đang tìm hiểu về một đồ thị vô hướng gồm \(n\) đỉnh, các đỉnh được nối với nhau bằng \(n - 1\) cạnh có trọng số sao cho từ một đỉnh có thể đi đến tất cả các đỉnh còn lại.

Bây giờ Giang sẽ thực hiện một số truy vấn trên đồ thị, cụ thể anh sẽ thực hiện \(q\) truy vấn. Giả sử đồ thị có một tập các đỉnh đặc biệt, đỉnh G của đồ thị (được đặt theo tên viết tắt của anh) lúc này được định nghĩa là đỉnh có tổng khoảng cách đến tất cả các đỉnh đặc biệt là bé nhất (có thể tồn tại nhiều đỉnh G), giá trị G chính là tổng khoảng cách của đỉnh G đến tất cả các đỉnh đặc biệt.

Bây giờ với mỗi truy vấn, anh sẽ chọn ra \(m\) đỉnh trên đồ thị lần lượt là \(a_{1}, a_{2}, a_{3}, \ldots, a_{m}\). Với mỗi giá trị \(x\) sao cho \(1 \leq x \leq m\), Giang yêu cầu bạn tính giá trị G nếu tập đỉnh đặc biệt là \(a_{1}, a_{2}, \ldots, 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})\).
• 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})\) biểu thị có cạnh nối hai đỉnh \(u\) và \(v\) với trọng số là \(w\).
• \(q\) dòng tiếp theo là các truy vấn, mỗi truy vấn gồm một dòng bắt đầu bởi số nguyên \(m\) \((1 \leq m \leq n)\) là độ dài của dãy \(a\), tiếp sau đó lần lượt là dãy \(a_{1}, a_{2}, \ldots, a_{m}\) \((1 \leq a_i \leq n, a_i \neq a_j \ \forall i \neq j)\). Gọi \(M\) là tổng giá trị \(m\) trong tất cả truy vấn, dữ liệu đảm bảo rằng \(M \leq 6 \times 10^{5}\).

Output

• Gồm \(q\) dòng, mỗi dòng gồm \(m\) số lần lượt là giá trị G cho các số \(x\) từ \(1\) đến \(m\) nếu chọn tập \(a_{1}, a_{2}, \ldots, a_{x}\) làm các đỉnh đặc biệt.

Ví dụ

Input

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

Output

0 4 4 5 7 
0 3 5 7

Giải thích

Ràng buộc

• Subtask \(1\) (\(17\%\) số điểm): \(n, M \leq 5000\);
• Subtask \(2\) (\(19\%\) số điểm): Cây có dạng đường thẳng;
• Subtask \(3\) (\(20\%\) số điểm): \(m = 3\) trong mỗi truy vấn;
• Subtask \(4\) (\(21\%\) số điểm): \(w = 1\) trong mỗi cạnh;
• Subtask \(5\) (\(23\%\) số điểm): Không có ràng buộc gì thêm.