题目描述

NowLand 的高速公路系统已经使用了几十年，需要进行升级。

在这个国家，有 $n$ 个城市和 $m$ 条单向高速公路，这些高速公路从一个城市通往另一个城市。一辆车可以使用第 $i$ 条高速公路在 $t_i$ 分钟内从城市 $u_i$ 到达城市 $v_i$。一次关于这条公路的高速公路升级可以将其用时减少 $w_i$ 分钟。每条高速公路都可以进行多次升级。

作为一个自私的人，NowLand 的总统只考虑自己的利益。升级高速公路系统是他最后的工作，之后他就退休了。退休后，他将从 NowLand 的首都城市 $1$ 出发前往城市 $n$，在那里度过余生。在这次旅行中，他只会使用高速公路，因此他只关心从城市 $1$ 到城市 $n$ 的时间，并希望尽可能缩短它。

但是由于政府没有足够的资金，因此高速公路升级的预算是有限的。在预算尚未确定的情况下，总要为不同的情况做好准备。于是，他想知道，如果他可以进行 $k$ 次升级，那么他从城市 $1$ 到城市 $n$ 的最短时间是多少呢？

可以保证，使用高速公路可以从城市 $1$ 到达城市 $n$。

输入格式

每组测试包含多个测试用例。第一行包含测试用例的数量 $T (1 \leq T \leq 10^4)$。

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

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

从第 $2$ 行到第 $(m+1)$ 行的每一行包含 4 个整数 $u_i, v_i, t_i, w_i (1 \leq u_i, v_i \leq n, u_i \neq v_i, 2 \leq t_i \leq 10^{12}, 1 \leq w_i \leq \min(t_i - 1, 10^9))$，表示第 $i$ 条高速公路的起点、终点、原始旅行时间和每次升级减少的时间。可以保证可以使用高速公路从城市 1 旅行到城市 $n$。

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

从第 $(m+3)$ 行到第 $(m+q+2)$ 行的每一行包含一个整数 $k_i (1 \leq k_i \leq 10^9)$，表示升级的次数。保证 $\forall 1 \leq j \leq m, t_j - w_j \times k_i > 0$。

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

输出格式

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

1
4 4
1 2 15 1
1 3 20 2
2 4 10 1
3 4 10 1
2
9
1

12
24