В первой строке задано единственное число $t$ ($1 \leq t \leq 10000$)~--- количество наборов входных данных. Затем следует их описание.

В первой строке каждого набора входных данных заданы $n$ ($1 \leq n \leq 2 \cdot 10^5$) и $m$ ($0 \leq m \leq 2 \cdot 10^5$)~--- количество зал и тоннелей в графе.

Во второй строке каждого набора входных данных заданы таинственные числа $c_1, c_2, \ldots, c_n$ ($0 \leq c_i \leq 10^9$).

В следующих $m$ строках идёт описание тоннелей.

Каждый тоннель задан в отдельной строке числами $u_i, v_i$ ($1 \leq u_i, v_i \leq n$) и $w_i$ ($0 \leq w_i \leq 10^9$)~--- означающие тоннель между вершинами $u_i, v_i$ длины $w_i$.

Гарантируется, что каждый тест задает корректный лабиринт --- граф без петель и кратных рёбер, и что сумма $n$ и $m$ по отдельности по всем наборам входных данных не превосходит $2 \cdot 10^5$.
