\begin{problem}{Полный назад! Самый полный назад!}{стандартный ввод}{стандартный вывод}{2 секунды}{256 мегабайт}

Регата стартовала, и кругосветная гонка в самом разгаре. Экипаж <<Беды>>, состоящий из капитана Врунгеля, студента Лома и шулера Фукса, настроен на победу. В зоне видимости экипажа находятся $n$ островов. Из-за розы ветров и подводных течений количество фарватеров (прямых маршрутов между островами) ограничено. Капитан обнаружил $m$ направленных фарватеров, $j$-й фарватер позволяет добраться с острова $v_j$ на остров $u_j$ и имеет длину $w_j$.

Некоторые фарватеры находятся в зоне \textit{мёртвого штиля}. После \textbf{каждого} перемещения <<Беды>> направление такого фарватера меняется на противоположное. Например, если фарватер $2 \to 4$ длины $1$ находится в зоне \textit{мёртвого штиля}, после первого перемещения <<Беды>> по любому фарватеру он превратится в фарватер $4 \to 2$ длины $1$, после второго~--- в фарватер $2 \to 4$ длины $1$, и так далее.

Останавливаться на островах необходимо для пополнения запасов. Помогите капитану Врунгелю найти кратчайшее расстояние от острова $1$ до всех остальных. Расстояние считается как сумма длин пройденных фарватеров.

\begin{center}
\includegraphics{pic3.png}
\end{center}


\InputFile
В первой строке дано целое число $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$.


\OutputFile
Для каждого набора входных данных выведите $n$ целых чисел --- кратчайшие расстояния от острова номер $1$ до островов $1, 2, \ldots, n$. Если невозможно добраться до какого-то острова, вместо расстояния до него выведите $-1$.


\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\end{problem}

