题目描述

本题译自 CCO 2014 Day1 T2「King Gruff」

狼国王格鲁夫统治着一个居住着可爱的狐狸的繁荣、快乐的领地。对狐狸们来说，不幸的是，他根本不是一个好国王，而且还想让他们的生活过得很惨。

他的国家有 $N$ 个城市，由 $M$ 条路连接，第 $i$ 条路可以让你从城市 $X_i$ 走到另一个城市 $Y_i$，并且只能往这个方向走，这条路的长度为 $L_i$，关闭费为 $C_i$，可能会有多条道路以相同的方向连接着两个相同的城市。

国王格鲁夫尤其不喜欢住在两个不同城市 $A$ 和 $B$ 里的狐狸并且想让他们从城市 $A$ 到城市 $B$ 很麻烦甚至根本行不通。具体来说，他将选择一个距离 $D$，并且同时关闭某些他王国里的路。关闭的条件是，如果这条路是城市 $A$ 到城市 $B$ 路径上的一部分且该路径总长不超过 $D$。对于每条这样的路，他将用皇家金库里的钱取支付它的关闭费。一个路径包含一个路的序列，除了第一条路外，每条路起点在前一条路的终点，并且可能多次访问同一个城市或走同一条路。

格鲁夫正在纠结选哪个 $D$，不管怎样，大一些的 $D$ 值可以使得他的狐狸子民更加不方便，但是可能花费他更多的钱！因此，他想了 $Q$ 个不同的值 $D_1,D_2,...,D_Q$，对于每一个值，他想知道需要花费多少来满足他的要求。因为你也不喜欢狐狸，你同意帮他写个程序计算最小花费。

输入格式

第一行包括四个由空格分隔的整数 $N,M,A,B$，城市数，道路数，开始城市，结束城市。

接下来 $M$ 行四个空格分隔的整数 $X_i,Y_i,L_i,C_i$，表示一条从 $X_i$ 到 $Y_i$ 的长为 $L_i$ 的路，它的关闭费为 $C_i$。

接下来一行一个数 $Q$，表示询问个数。

接下来 $Q$ 行包含一个数 $D_i$ 表示题中所述距离参数。

输出格式

输出包括 $Q$ 行，表示根据距离参数 $D_i(1\le i\le Q)$ 求出的关闭所有必要的路的总花费。

4 5 1 3
1 2 5 1
1 2 8 50
2 3 2 15
3 1 80 1000
3 4 1 1
4
8
6
90
94

16
0
66
1066

4 3 1 2
2 1 1 1
3 4 10000 10000
4 3 10000 10000
1
1000000000

0

提示

王国如下图所示，每条路只标注了长度。

如果 $D=8$，第一、三条路需要被关闭，他们都是从城市 $1$ 到 城市 $3$ 的长为 $7$ 的路径的一部分，总花费 $1+15=16$。

如果 $D=6$，不需要关闭任何路，因为没有从城市 $1$ 到城市 $3$ 的路长度小于或等于 $6$。

如果 $D=90$，前三条路都要被关闭。

如果 $D=94$，第四条路也要被关闭，因为它在城市 $1$ 到城市 $3$ 的路径上，该路径长度刚好为 $94$，路径为依次走第一、三、四、一、三条路。

王国如下图所示

就像你所看到的一样，狐狸已经有麻烦了，因为这里根本没有从城市 $1$ 到城市 $2$ 的路径，因此对于任何 $D$ 格鲁夫国王都不需要关闭任何道路。

对于至多 $20\%$ 的数据，$1\le N\le 500$；

对于至多 $20\%$ 的数据，$Q=1$；

对于至多 $80\%$ 的数据，$1\le Q\le 20$；

对于 $100\%$ 的数据，$1\le X_i,Y_i,A,B\le N \le 10^5,$ $0\le M\le 10^5,$ $1\le L_i,C_i\le 10^4,$ $1\le Q\le 10^5,$ $1\le D\le 10^9$。