CF2239E.The end of this world,

... and the girl who crossed the moon's oceans.

— Frums

You are given an undirected graph consisting of $n$ vertices and $m$ edges. The $i$-th vertex has an associated value $\mathrm{val}_i$. The $j$-th edge connects vertices $u_j$ and $v_j$ and has two properties: a capacity $w_j$ and a floor $\mathrm{low}_j$. It is guaranteed that $w_j \ge \mathrm{low}_j$ for all edges.

You want to start a walk from a vertex $s$. Before the walk begins, you must choose an arbitrary non-negative integer $h_{start}$ as your initial state parameter.

If you are currently at vertex $u$ with state $h$, you can traverse an edge $j$ connecting $u$ and $v$ if and only if $w_j \ge h$. Upon traversing this edge and arriving at vertex $v$, the state parameter $h$ updates to $\max(h, \mathrm{low}_j)$.

Let the walk end at some vertex $t$. You must traverse at least one edge. The score of such a walk is defined as $\mathrm{val}_t + h_{start}$. Note that we are interested in the sum of the final vertex value and the initial state parameter, not the final state parameter.

For each starting vertex $s$ from $1$ to $n$, calculate the maximum possible score achievable. If it is impossible to traverse any edge starting from some $s$, output $-1$ instead.

……以及那位穿越月球海洋的女孩。

— Frums

给定一个包含 $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$ 时，你才能沿第 $j$ 条边（连接 $u$ 和 $v$）行进。当你经该边抵达顶点 $v$ 后，状态参数 $h$ 更新为 $\max(h, \mathrm{low}_j)$。

设该行走终止于某个顶点 $t$。你必须至少经过一条边。此类行走的得分定义为 $\mathrm{val}_t + h_{start}$。注意：我们关心的是终点顶点的值与初始状态参数之和，而非最终状态参数。

对每个起始顶点 $s$（从 $1$ 到 $n$），计算所能达到的最大得分。若从某个 $s$ 出发无法经过任何边，则输出 $-1$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 5\cdot 10^5, 0 \le m \le 5\cdot 10^5$) — the number of vertices and the number of edges.

The second line of each test case contains $n$ integers $\mathrm{val}_1, \mathrm{val}_2, \ldots, \mathrm{val}_n$ ($1 \le \mathrm{val}_i \le 10^9$) — the values of the vertices.

The next $m$ lines describe the edges. The $j$-th line contains four integers $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$) — the endpoints and properties of the $j$-th edge.

The graph is not guaranteed to be connected and may contain multiple edges.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, output $n$ integers separated by spaces. The $i$-th integer should be the maximum score achievable starting from vertex $i$, or $-1$ if no edge can be traversed.

对于每个测试用例，输出 $n$ 个由空格分隔的整数。其中第 $i$ 个整数应为从顶点 $i$ 出发所能获得的最大得分；若无法遍历任何一条边，则输出 $-1$。

In the first test case, here are the optimal $h_{start}$ values and paths for each starting node:

• For node $1$, it is optimal to use $h_{start}=5$. Then, take the path from node $1$ to node $2$. $h$ is updated to $\operatorname{max}(5,2)=5$. The path ends, and the score is $20+5=25$.
• For node $2$, it is optimal to use $h_{start}=5$. Then, take the path from node $2$ to node $1$, then from node $1$ to node $2$. The score is $20+5=25$.
• For node $3$, it is optimal to use $h_{start}=4$. Then, take the path from node $3$ to node $2$. The score is $20+4=24$.

In the third test case, since there are no edges incident to either node, the answer is $-1$ for both.

在第一个测试用例中，每个起始节点对应的最优 $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$ 或节点 $2$ 关联，因此两者的答案均为 $-1$。