Đất nước JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, được đánh số từ \(1\) đến \(N-1\). Đường thứ \(i\) có hai làn: một làn đi từ thành phố \(A_i\) đến thành phố \(B_i\) và một làn đi theo chiều ngược lại. Như vậy, mọi con đường đều đi được theo hai chiều. Có thể đi giữa hai thành phố bất kỳ bằng các con đường này.

Hiện tại, chưa có làn đường nào được trải nhựa. Trên đường thứ \(i\), chi phí trải nhựa làn từ \(A_i\) đến \(B_i\) là \(C_i\), còn chi phí trải nhựa làn từ \(B_i\) đến \(A_i\) là \(D_i\).

Ông K, thủ tướng đất nước JOI, có thể chọn một số thành phố để chỉ định làm thành phố nghỉ dưỡng. Khi thành phố \(x\) được chỉ định, với mỗi đường thứ \(i\), điều sau sẽ xảy ra: trong hai thành phố \(A_i\) và \(B_i\), gọi thành phố gần \(x\) hơn là \(a\), thành phố xa \(x\) hơn là \(b\). Ở đây, gần hơn có nghĩa là cần đi qua ít con đường hơn để đến \(x\). Khi đó, làn đường từ \(b\) đến \(a\) sẽ được trải nhựa nếu làn đó chưa được trải nhựa.

Chi phí trải nhựa các làn đường do việc chỉ định thành phố nghỉ dưỡng sẽ được chi trả bằng tiền thuế. Tuy nhiên, ông K phải dùng tiền túi của mình để trải nhựa tất cả các làn đường vẫn chưa được trải nhựa sau khi việc chỉ định kết thúc.

Có \(Q\) phương án được đề xuất. Trong phương án thứ \(j\), xuất phát từ trạng thái chưa có thành phố nghỉ dưỡng và chưa có làn đường nào được trải nhựa, ông K sẽ chỉ định đúng \(E_j\) thành phố làm thành phố nghỉ dưỡng. Những thành phố cụ thể chưa được chọn. Với mỗi phương án, hãy tính tổng chi phí nhỏ nhất mà ông K phải tự chi trả.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N
A_1 B_1 C_1 D_1
...
A_{N-1} B_{N-1} C_{N-1} D_{N-1}
Q
E_1
...
E_Q

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa tổng chi phí nhỏ nhất ông K phải tự chi trả trong phương án thứ \(j\).

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\) với \(1 \le i \le N-1\).
• Có thể đi giữa hai thành phố bất kỳ bằng các con đường đã cho.
• \(1 \le C_i,D_i \le 1\,000\,000\,000\) với \(1 \le i \le N-1\).
• \(1 \le Q \le N\).
• \(1 \le E_j \le N\) với \(1 \le j \le Q\).

Phân nhóm

1. \(6\) điểm: \(N \le 16\).
2. \(7\) điểm: \(Q=1\) và \(E_1=1\).
3. \(9\) điểm: \(Q=1\) và \(E_1=2\).
4. \(17\) điểm: \(N \le 2\,000\).
5. \(17\) điểm: \(Q=1\).
6. \(44\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2

9
1

5
1 3 13 6
5 1 17 8
5 2 6 10
1 4 16 11
1
1

36

6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
1
2

14

15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7

44
12
6

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 3 (22/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.