Giải bài trực tuyến

Cho một đồ thị vô hướng có trọng số, với trọng số cạnh thể hiện khả năng thông qua của cạnh đó.

Bây giờ cho một số x, hãy tính xem có bao nhiêu cặp (s, t) không tính thứ tự trong đồ thị thỏa mãn minCut(s,t) <= x.

Một nhát cắt là một cách chia các đỉnh của đồ thị thành 2 tập hợp sao cho s và t thuộc 2 tập khác nhau sau khi chia.

Trong đồ thị có trọng số, độ lớn của một nhát cắt được định nghĩa là tổng trọng số của các cạnh bị nhát cắt cắt qua. minCut là một nhát cắt có độ lớn nhỏ nhất có thể.

Input

Dòng đầu chứa T, số lượng test.

Với mỗi test, dòng đầu chứa 2 số nguyên n và m, thể hiện số lượng đỉnh và số lượng cạnh của đồ thị.

m dòng tiếp theo, mỗi dòng chứa 3 số nguyên u,v,c thể hiện một cạnh vô hướng với khả năng thông qua c giữa đỉnh u và v; 1 <= u,v <= n.

Dòng tiếp theo chứa q, số lượng câu hỏi. q dòng tiếp theo, mỗi dòng chứa một số nguyên x.

Lưu ý: có thể có nhiều cạnh giữa một cặp đỉnh.

Output

Chứa q dòng, mỗi dòng chứa 1 số nguyên thể hiện số lượng cặp không thứ tự (s, t) tương ứng cho câu hỏi đó. In ra một dòng trống giữa các test.

Lưu ý: Time limit cho bài này khá chặt.

Example

Input:
1
5 0
1
0

Output:
10

Constraints

Input Set 1: Số lượng test <= 15, n <= 40, m <= 400, q <= 10

Input Set 2: Số lượng test <= 20, n <= 150, m <= 3000, q <= 30

Trọng số các cạnh không quá 10^6.