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