题目描述

NowLand的高速公路系统已经使用了相当长的一段时间，需要进行升级。

在这个国家，有 $n$ 个城市以及 $m$ 条单程高速公路，这些公路连接着各个城市。使用第 $i$ 条高速公路，一辆车可以从城市 $u_i$ 行驶至城市 $v_i$ ，所需时间为 $t_i$ 分钟。一次升级可以缩短 $w_i$ 分钟的路程时间。每条高速公路可以按照你的意愿进行多次升级。

作为一位自私的人，NowLand公司的总裁只考虑自己的利益。在完成升级高速公路的任务之后他将退休。退休后，他将离开NowLand的首都城市 $1$ ，前往城市 $n$，并在那里度过余生。他只会行驶在高速公路来完成这段旅程，因此他只关心从城市 $1$ 到达城市 $n$ 所需的时间，并希望这段旅程尽可能地短。

但由于政府资金不足，升级预算有限。在预算尚未确定的情况下，总统需要为各种情况做好准备。所以他想要知道，如果他能进行 $K$ 次升级，从城市 $1$ 到达城市 $n$ 所需的最短时间是多少。

数据保证总能通过高速公路从城市 $1$ 到达城市 $n$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1≤t≤10^4)$。

每个测试用例由多行组成。

第一行包含两个整数 $n$ 和 $m(4≤n≤10^5,1≤m≤3\times 10^5)$ ，表示国家中的城市和高速公路的数量。

从第 $2$ 行到第 $m+1$ 行，每一行包含4个整数 $u_i,v_i,t_i,w_i (1≤ u_i,v_i ≤ n,u_i≠v_i,2≤t_i≤10^{12}.1≤w_i≤min(t_i-1,10^9))$ ，分别表示第 $i$ 条高速公路的起点、终点、原始行驶时间和升级参数。

第 $m+2$ 行包含一个整数 $q(1≤ q≤ 3\times 10^5)$，表示要询问的查询次数。

从第 $m+3$ 行到第 $m+q+2$ 行中的每一行都包含一个整数 $k(1≤k≤10^9)$ ，即升级的次数。保证对于任意的$1≤j≤m，都有t_j-w_j\times k>0$。

可以保证，在一个测试用例中，$\sum n$的值不会超过 $2\times 10^5$，而所有测试用例中 $\sum m$ 和 $\sum q$ 的值不会超过 $6\times 10^5$。

输出格式

对于每个测试用例，输出 $q$ 个整数：从城市 $1$ 到城市 $n$ 使用 $k_i$ 次升级的最短旅行时间。

样例

1
4 5
1 2 10 2
2 3 10 1
3 4 10 3
1 3 20 1
2 4 30 2
3
1
2
3

27
24
21