King Gruff

This problem is translated from CCO 2014 Day1 T2 "King Gruff".

In a kingdom with $N$ cities and $M$ directed roads, each road from city $X_i$ to $Y_i$ has a length $L_i$ and a closing fee $C_i$. The despised foxes reside in two different cities $A$ and $B$. To make their journey from $A$ to $B$ as troublesome as possible, King Gruff chooses a distance $D$ and simultaneously closes all roads that lie on some $A$–$B$ path with total length at most $D$. A path is defined as a sequence of roads (possibly revisiting cities or reusing roads) where, except for the first road, every road starts at the endpoint of the previous road.

The key observation is that a road from $u$ to $v$ will be closed if and only if there exists an $A$–$B$ path that uses this road and whose total length is at most $D$. This can be checked by verifying whether [ \text{dist}(A,u) + L_{(u\to v)} + \text{dist}(v,B) \le D, ] where (\text{dist}(X,Y)) denotes the shortest distance from city (X) to city (Y).

Your task is to, given several queries with different values of $D$, compute the minimum total cost the king must incur, i.e. the sum of closure fees of all roads that satisfy the above condition.

inputFormat

The first line contains four integers $N$, $M$, $A$, $B$, representing the number of cities, the number of roads, the starting city, and the destination city respectively.

Each of the next $M$ lines contains four integers $X$, $Y$, $L$, $C$, indicating there is a directed road from city $X$ to city $Y$ with length $L$ and closing fee $C$.

The next line contains an integer $Q$, the number of queries.

Each of the following $Q$ lines contains a single integer $D$.

outputFormat

For each query, output a single integer — the minimum total cost required to close all roads that are part of an $A$–$B$ path with total length at most $D$.

sample

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

5
11
11