Беспорядки в Барбилэнде
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, Барбилэнд — прекрасное место, в котором все идеально, и все занимаются тем, чем должны заниматься по задумке своих создателей, компании «Mattel». Вот только Кену Стереотипной Барби не хватает общения с ней, поэтому он в какой-то момент решил проанализировать граф знакомств между всеми жителями Барбилэнда, чтобы понять, почему ему так одиноко. Несмотря на то, что ему это не помогло, опишем несколько фактов, которые он выяснил.

Всего в Барбилэнде ровно $$$n$$$ жителей, и среди них ровно $$$m$$$ пар общающихся друг с другом. У каждого жителя $$$v$$$ есть показатель статуса в обществе $$$p_v$$$, а у каждой пары общающихся жителей $$$(u, v)$$$ — показатель близости $$$d_{u,v}$$$. Тогда недовольство жителя $$$v$$$ вычисляется как $$$$$$s_v = \sum\limits_{(u, v)} p_v \oplus d_{u,v} \text{,}$$$$$$ где за $$$\oplus$$$ обозначена операция xor (побитовое исключающее «ИЛИ»). Общее недовольство всех жителей вычисляется как сумма значений недовольства по всем жителям Барбилэнда.

После нескольких перемещений Кена и Барби между Барбилэндом и реальным миром, как мы знаем, весь Барбилэнд был в хаосе: несколько смен режима, многие пары разругались, и это еще только вершина айсберга! Пока все не вернулось в более спокойное состояние, было решено во избежание новых проблем временно запретить общение некоторым парам жителей, то есть удалить ребра из графа знакомств. При этом граф знакомств должен остаться связным, чтобы общество не раскололось на нексколько независимых групп.

Тут то и пригодится информация, собранная Кеном ранее! Определите, какого минимального суммарного недовольства жителей можно добиться, удалив некоторые ребра из графа знакомств (общения), чтобы при этом для любых двух жителей все еще существовала цепочка общения, приводящая от одного к другому.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — количество жителей и общавшихся пар ($$$1 \le n, m \le 2 \cdot 10^5$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$p_i$$$ — статус в обществе каждого жителя $$$(0 \le p_i \le 10^9$$$).

В следующих $$$m$$$ строках перечислены ребра графа, по одному на строке. Каждая строка содержит три целых числа $$$v_i$$$, $$$u_i$$$ и $$$d_{u_i, v_i}$$$, означающих, что жители $$$u_i$$$ и $$$v_i$$$ общаются с близостью $$$d_{u_i, v_i}$$$ ($$$1 \le u_i, v_i \le n$$$; $$$0 \le d_{u_i, v_i} \le 10^9$$$).

Гарантируется, что $$$u_i \ne v_i$$$ для всех $$$i$$$, и что граф связен. Кратные ребра не запрещаются.

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

Выведите единственное целое число — минимальное возможное суммарное недовольство, которого можно добиться, удалив некоторые ребра графа, и при этом оставив его связным.

Примеры

Входные данные
4 5
1 1 4 1
1 2 2
1 3 2
1 4 3
2 3 5
3 4 2
Выходные данные
15
Входные данные
3 3
1 4 16
1 2 17
2 3 17
1 3 17
Выходные данные
39

Примечание

Во втором примере выгодно выбрать ребра $$$1 \leftrightarrow 3$$$ и $$$2 \leftrightarrow 3$$$. Тогда недовольство первого жителя равно $$$1 \oplus 17 = 16$$$, второго — $$$4 \oplus 17 = 21$$$, а третьего — дважды по $$$16 \oplus 17 = 1$$$, так как веса всех ребер равны. Сумма получается равна $$$39$$$.