CF2239E The end of this world,

:::epigraph[— Frums] [... and the girl who crossed the moon's oceans.](https://music.163.com/#/song?id=528271201) （终末横渡月海少女） ::: 给定一个包含 $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}$ 作为你的初始状态参数（你可以自由选择任意合法的值）。 如果你当前位于顶点 $u$，且当前的状态参数为 $h$，当且仅当 $w_j \ge h$ 时，你才能经过连接 $u$ 和 $v$ 的第 $j$ 条边。在经过这条边并到达顶点 $v$ 后，状态参数 $h$ 将更新为 $\max(h, \mathrm{low}_j)$。 假设游走最终在某个顶点 $t$ 结束。你必须至少经过一条边（即游走长度不能为 $0$）。这样一次游走的得分定义为 $\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$。

在第一个测试用例中，对于每个起始节点，最优的 $h_{start}$ 取值和游走路径如下： - 对于节点 $1$，最优选择是令 $h_{start}=5$。然后，走从节点 $1$ 到节点 $2$ 的路径。此时 $h$ 被更新为 $\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$。 翻译基本由 Qwen3.7-Plus 完成。