늑대 왕 그러프

늑대 왕 그러프는 N개 도시와 M개의 일방통행 도로가 있는 나라를 다스립니다. i번 도로는 Xi에서 Yi로 가며 길이 Li, 폐쇄 비용 Ci가 있습니다. 두 도시 A와 B 사이를 불편하게 만들기 위해 거리 한도 D를 정하고, A에서 B까지 길이가 D 이하인 경로에 포함되는 모든 도로를 동시에 폐쇄합니다. Q개의 서로 다른 D 값마다 필요한 총 폐쇄 비용을 구하세요.

첫 줄에 N, M, A, B가 있습니다. 다음 M줄에 Xi, Yi, Li, Ci가 주어집니다. 그다음 Q가 있고, Q줄에 각 Di가 주어집니다.

각 Di에 대해 폐쇄해야 하는 도로의 비용 합을 한 줄씩 출력합니다.