E. The end of this world,

Source: Codeforces 2239E
Contest: Codeforces Round 1105 (Div. 1)
Time limit: 5 seconds
Memory limit: 1024 megabytes

Statement

... 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.

Input

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$.

Output

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.

Note

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.

Examples

9
3 2
10 20 5
1 2 5 2
2 3 4 3
2 1
100 10
1 2 10 5
2 0
50 50
1 0
114514
4 1
1 2 3 4
3 4 2 1
3 2
1 4 1
1 3 4 1
1 2 2 1
3 2
10 3 2
2 3 4 4
2 1 3 2
3 2
5 2 2
3 2 4 4
1 3 5 5
5 9
857147200 381798978 633421584 956726892 315899900
2 1 883474754 795831571
2 4 657281748 375466725
1 3 666641114 444218918
2 3 901861650 790895313
3 2 613790652 96876004
2 5 852725279 216601090
3 4 500240642 193633892
2 5 210434355 130646156
3 2 457018372 279005896

25 25 24
110 110
-1 -1
-1
-1 -1 6 6
6 6 6
13 13 7
10 9 10
1740621954 1740621954 1740621954 1614008640 1709872479