Регата стартовала, и кругосветная гонка в самом разгаре. Экипаж «Беды», состоящий из капитана Врунгеля, студента Лома и шулера Фукса, настроен на победу. В зоне видимости экипажа находятся $$$n$$$ островов. Из-за розы ветров и подводных течений количество фарватеров (прямых маршрутов между островами) ограничено. Капитан обнаружил $$$m$$$ направленных фарватеров, $$$j$$$-й фарватер позволяет добраться с острова $$$v_j$$$ на остров $$$u_j$$$ и имеет длину $$$w_j$$$.
Некоторые фарватеры находятся в зоне мёртвого штиля. После каждого перемещения «Беды» направление такого фарватера меняется на противоположное. Например, если фарватер $$$2 \to 4$$$ длины $$$1$$$ находится в зоне мёртвого штиля, после первого перемещения «Беды» по любому фарватеру он превратится в фарватер $$$4 \to 2$$$ длины $$$1$$$, после второго — в фарватер $$$2 \to 4$$$ длины $$$1$$$, и так далее.
Останавливаться на островах необходимо для пополнения запасов. Помогите капитану Врунгелю найти кратчайшее расстояние от острова $$$1$$$ до всех остальных. Расстояние считается как сумма длин пройденных фарватеров.
В первой строке дано целое число $$$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$$$-й фарватер находится в зоне мертвого штиля, в противном случае — нет.
В следующих $$$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$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел — кратчайшие расстояния от острова номер $$$1$$$ до островов $$$1, 2, \ldots, n$$$. Если невозможно добраться до какого-то острова, вместо расстояния до него выведите $$$-1$$$.
34 400011 2 31 3 53 2 62 4 14 5001011 2 22 3 44 3 53 2 12 4 23 2011 2 12 3 2
0 3 5 120 2 6 -10 1 -1
