Thị trấn JOI từng là một khu công nghiệp phát triển. Nhiều nhà ga và tuyến đường sắt đã được xây dựng để vận chuyển hàng hóa. Khi thị trấn suy thoái, những nhà ga và tuyến đường sắt này không còn được sử dụng, nhưng vẫn còn tồn tại.

Có \(N\) nhà ga, được đánh số từ \(1\) đến \(N\), và \(M\) tuyến đường sắt. Tuyến thứ \(i\) nối hai chiều giữa ga \(A_i\) và ga \(B_i\), có khổ đường là \(W_i\). Có thể đi từ một ga bất kỳ đến mọi ga khác bằng các tuyến đường sắt hiện có.

Là thị trưởng, bạn muốn tận dụng hệ thống này để thu hút một công ty đường sắt và hồi sinh thị trấn. Có \(Q\) công ty đăng ký tham gia dự án. Tuy nhiên, các công ty sử dụng tàu có khổ đường khác nhau, nên cần cải tạo một số tuyến đường sắt cho phù hợp.

Công ty thứ \(j\) sử dụng khổ đường \(X_j\). Để thu hút công ty này, phải bảo đảm rằng có thể đi từ bất kỳ ga nào đến bất kỳ ga nào khác chỉ bằng những tuyến đường sắt có khổ đường \(X_j\).

Bạn được thực hiện thao tác cải tạo sau tùy ý nhiều lần: chọn một tuyến đường sắt rồi tăng hoặc giảm khổ đường của tuyến đó đi \(1\), với chi phí \(1\). Nếu khổ đường hiện tại bằng \(1\) thì không được giảm thêm.

Để quyết định lựa chọn công ty nào, hãy tính chi phí nhỏ nhất cần bỏ ra cho từng công ty. Chi phí cho mỗi công ty được tính độc lập, bắt đầu từ hệ thống đường sắt ban đầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng:

N M
A_1 B_1 W_1
A_2 B_2 W_2
...
A_M B_M W_M
Q
X_1
X_2
...
X_Q

Mọi giá trị đầu vào đều là số nguyên.

Dữ liệu ra

Xuất \(Q\) dòng. Dòng thứ \(j\) chứa chi phí nhỏ nhất cần bỏ ra để thu hút công ty thứ \(j\).

Ràng buộc

• \(2\le N\le 500\).
• \(N-1\le M\le 100\,000\).
• \(1\le Q\le 1\,000\,000\).
• \(1\le A_i<B_i\le N\) với mọi \(1\le i\le M\).
• \(1\le W_i\le 10^9\) với mọi \(1\le i\le M\).
• \((A_i,B_i,W_i)\ne(A_j,B_j,W_j)\) với mọi \(1\le i<j\le M\). Hai ga có thể được nối bằng nhiều tuyến có khổ đường khác nhau.
• Có thể đi từ bất kỳ ga nào đến bất kỳ ga nào khác bằng các tuyến đường sắt hiện có.
• \(1\le X_j\le 10^9\) với mọi \(1\le j\le Q\).
• \(X_j<X_{j+1}\) với mọi \(1\le j<Q\).

Phân nhóm

1. \(3\) điểm: \(M\le 16\), \(Q\le 10\).
2. \(4\) điểm: \(Q\le 10\).
3. \(7\) điểm: \(B_i=A_i+1\) với mọi \(1\le i\le M\).
4. \(28\) điểm: \(M\le 1000\).
5. \(35\) điểm: \(Q\le 20\,000\).
6. \(23\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

8
2
5
10
9
21

3 4
1 2 1
1 2 4
2 3 2
2 3 4
4
1
2
3
4

1
1
2
0

10 20
6 7 914727791
1 8 771674531
3 5 632918108
5 9 329296846
1 7 237501112
4 9 303328173
2 6 216298255
2 10 504024991
3 8 158236886
1 10 10176179
8 9 918271145
3 6 217165898
3 6 624543444
4 9 70147274
8 9 976983490
6 9 210108505
2 9 972711062
1 10 564567289
3 7 411395464
4 7 952470985
10
115721165
198969744
356664401
429802521
513343279
610443927
741016686
786597783
898772266
903568946

1121073688
761832468
1026806785
1316097872
1321500065
1445238392
1637513141
1621778548
1733953031
1738749711

Nguồn

Nguồn: JOI 2021/2022, Spring Training Camp, Contest 4. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.