给定一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的无向图。第 $$$i$$$ 个顶点具有关联值 $$$\mathrm{val}_i$$$。第 $$$j$$$ 条边连接顶点 $$$u_j$$$ 和 $$$v_j$$$,并具有两个属性:容量 $$$w_j$$$ 和下限 $$$\mathrm{low}_j$$$。保证所有边的 $$$w_j \ge \mathrm{low}_j$$$ 。
您想要从顶点 $$$s$$$ 开始行走。在步行开始之前,您必须选择任意非负整数 $$$h_{start}$$$ 作为初始状态参数。
如果当前位于状态为 $$$h$$$ 的顶点 $$$u$$$,则可以遍历连接 $$$u$$$ 和 $$$v$$$ 的边 $$$j$$$ 当且仅当 $$$w_j \ge h$$$。遍历这条边并到达顶点 $$$v$$$ 后,状态参数 $$$h$$$ 更新为 $$$\max(h, \mathrm{low}_j)$$$。
让行走在某个顶点 $$$t$$$ 处结束。你必须穿越 至少一条边 这种步行的。的 分数 本实验的 定义为 $$$\mathrm{val}_t + h_{start}$$$。请注意,我们感兴趣的是 最终顶点值 和 初始状态参数,不是最终状态参数。
对于从 $$$1$$$ 到 $$$n$$$ 的每个起始顶点 $$$s$$$,计算可达到的最大可能分数。如果不可能从$$$s$$$开始遍历任何边,则输出$$$-1$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 5\cdot 10^5, 0 \le m \le 5\cdot 10^5$$$) — 顶点数和边数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$\mathrm{val}_1, \mathrm{val}_2, \ldots, \mathrm{val}_n$$$ ($$$1 \le \mathrm{val}_i \le 10^9$$$) — 顶点的值。
接下来的 $$$m$$$ 行描述了边缘。第 $$$j$$$ 行包含四个整数 $$$u_j, v_j, w_j, \mathrm{low}_j$$$ ($$$1 \le u_j, v_j \le n, u_j \neq v_j$$$; $$$1 \le \mathrm{low}_j \le w_j \le 10^9$$$) — 的端点和属性第 $$$j$$$ 条边。
该图不保证是连通的,并且可能包含多条边。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$5\cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个由空格分隔的整数。第 $$$i$$$ 个整数应该是从顶点 $$$i$$$ 开始可达到的最大分数,如果没有边可以遍历,则为 $$$-1$$$。
示例
输入复制
93 210 20 51 2 5 22 3 4 32 1100 101 2 10 52 050 501 01145144 11 2 3 43 4 2 13 21 4 11 3 4 11 2 2 13 210 3 22 3 4 42 1 3 23 25 2 23 2 4 41 3 5 55 9857147200 381798978 633421584 956726892 3158999002 1 883474754 7958315712 4 657281748 3754667251 3 666641114 4442189182 3 901861650 7908953133 2 613790652 968760042 5 852725279 2166010903 4 500240642 1936338922 5 210434355 1306461563 2 457018372 279005896
输出复制
25 25 24110 110-1 -1-1-1 -1 6 66 6 613 13 710 9 101740621954 1740621954 1740621954 1614008640 1709872479
注意
在第一个测试用例中,以下是每个起始节点的最佳 $$$h_{start}$$$ 值和路径:
- 对于节点$$$1$$$,最佳使用$$$h_{start}=5$$$。然后,获取从节点 $$$1$$$ 到节点 $$$2$$$ 的路径。 $$$h$$$ 更新为 $$$\operatorname{max}(5,2)=5$$$。路径结束,得分为$$$20+5=25$$$。
- 对于节点$$$2$$$,最佳使用$$$h_{start}=5$$$。然后,采用从节点 $$$2$$$ 到节点 $$$1$$$ 的路径,然后从节点 $$$1$$$ 到节点 $$$2$$$ 的路径。分数是$$$20+5=25$$$。
- 对于节点$$$3$$$,最佳使用$$$h_{start}=4$$$。然后,获取从节点 $$$3$$$ 到节点 $$$2$$$ 的路径。分数是$$$20+4=24$$$。
在第三个测试用例中,由于没有边与任一节点相关,因此两个节点的答案都是 $$$-1$$$。