Как известно, Барбилэнд — прекрасное место, в котором все идеально, и все занимаются тем, чем должны заниматься по задумке своих создателей, компании «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 51 1 4 11 2 21 3 21 4 32 3 53 4 2
15
3 31 4 161 2 172 3 171 3 17
39
Во втором примере выгодно выбрать ребра $$$1 \leftrightarrow 3$$$ и $$$2 \leftrightarrow 3$$$. Тогда недовольство первого жителя равно $$$1 \oplus 17 = 16$$$, второго — $$$4 \oplus 17 = 21$$$, а третьего — дважды по $$$16 \oplus 17 = 1$$$, так как веса всех ребер равны. Сумма получается равна $$$39$$$.