E. The end of this world,
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
... 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.

Example
Input
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
Output
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
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.