E. Конец этого мира,
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
... and the girl who crossed the moon's oceans.
— 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$$$, вы можете пройти по ребру $$$j$$$, соединяющему $$$u$$$ и $$$v$$$, тогда и только тогда, когда $$$w_j \ge h$$$. При прохождении этого ребра и прибытии в вершину $$$v$$$ параметр состояния $$$h$$$ обновляется до $$$\max(h, \mathrm{low}_j)$$$.

Пусть обход заканчивается в некоторой вершине $$$t$$$. Вы должны пройти хотя бы одно ребро. Счёт такого обхода определяется как $$$\mathrm{val}_t + h_{start}$$$. Обратите внимание, что нас интересует сумма значения конечной вершины и начального параметра состояния, а не конечного параметра состояния.

Для каждой начальной вершины $$$s$$$ от $$$1$$$ до $$$n$$$ вычислите максимально достижимый счёт. Если из некоторой вершины $$$s$$$ невозможно пройти ни по одному ребру, выведите $$$-1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел через пробел. $$$i$$$-е целое число должно быть равно максимальному счёту, достижимому из вершины $$$i$$$, или $$$-1$$$, если ни одно ребро не может быть пройдено.

Пример
Входные данные
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
Примечание

В первом наборе входных данных оптимальные значения $$$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$$$ для обеих вершин.