Kamome изучает треугольные пути во взвешенном неориентированном графе. В частности, путь называется треугольным, если выполняется одно из следующих условий:

• длина пути не превосходит 2, или
• для любых трех различных ребер $e_1, e_2, e_3$ на этом пути, веса $w(e_1), w(e_2), w(e_3)$ всегда могут образовать три стороны треугольника.

Напомним, что положительные целые числа $x, y, z$ могут образовать три стороны треугольника тогда и только тогда, когда выполняются $x < y + z$, $y < z + x$ и $z < x + y$.

Kamome дает вам взвешенный неориентированный граф. Для каждой пары вершин $(u, v)$ необходимо определить, существует ли треугольный путь, начинающийся в $u$ и заканчивающийся в $v$. Считается, что для каждой вершины треугольный путь от нее к самой себе всегда существует.

Рис. 1: Часть «треугольника» Пекинского университета

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке задано целое число $t$ ($1 \le t \le 10^5$) — количество наборов входных данных. Далее следует описание каждого набора.

Первая строка каждого набора содержит два целых числа $n$ и $m$ ($1 \le n, m \le 3000$, $1 < \sum n^2, \sum m^2 \le 3000^2$) — количество вершин и ребер графа.

Каждая из следующих $m$ строк содержит три целых числа $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$), описывающих ребро $(u_i, v_i)$ и его вес $w_i$.

Граф может быть несвязным, содержать повторяющиеся ребра или кратные ребра.

Выходные данные

Для каждого набора входных данных выведите $n$ строк. Каждая строка является строкой из $n$ символов, где $j$-й символ равен $s_{i,j}$. Если $s_{i,j} = \text{'0'}$, это означает, что не существует треугольного пути, начинающегося в $i$ и заканчивающегося в $j$; в противном случае выведите '1'.

Примеры

Пример ввода 1

2
4 3
1 2 2
1 2 2
2 3 2
3 2
1 2 3
2 3 2
3 4 3

Пример вывода 1

1111
1111
1111
1111
11101110
11111111

Пример ввода 2

3 2
1 2 3
2 3 4
3 4 1

Пример вывода 2

01111000
11111000
11100111

Пример ввода 3

2 6 2
1 2 6
6 7 4
6 8 5

Пример вывода 3

11100111
01100111