CF2239E The end of this world,

[... and the girl who crossed the moon's oceans.](https://music.163.com/#/song?id=528271201) — 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.

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

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.

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.