В первой строке дано целое число $t$ ($1 \le t \le 1000$) --- количество наборов входных данных.

В первой строке каждого набора даны два целых числа $n$, $m$ ($2 \le n \le 10^5, 1 \le m \le 2\cdot10^5$) --- количество островов и количество фарватеров.

Во второй строке каждого набора дана строка $s$ длины $m$, состоящая из нулей и единиц. Если $s_j = 1$, то $j$-й фарватер находится в зоне \textit{мертвого штиля}, в противном случае~--- нет.

В следующих $m$ строках каждого набора даны целые числа $v_j$, $u_j$, $w_j$ ($1 \le v_j, u_j \le n$, $1 \le w_j \le 10^6$) --- описание фарватеров.

Обратите внимание, что между одной парой островов может быть несколько фарватеров. Кроме того, возможны фарватеры из острова в него же.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2 \cdot 10^5$. Также гарантируется, что сумма $m$ по всем наборам входных данных не превосходит $4 \cdot 10^5$.
