Камоме зараз досліджує трикутні шляхи у зважених неорієнтованих графах. Точніше, шлях називається трикутним тоді й лише тоді, коли:

• Довжина цього шляху не перевищує $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$.

Камоме дав вам зважений неорієнтований граф. Вам потрібно для кожної пари вершин $(u, v)$ визначити, чи існує трикутний шлях, що починається в $u$ і закінчується в $v$. Вважаємо, що з кожної вершини в саму себе завжди існує трикутний шлях.

Вхідні дані

Кожен тест містить декілька наборів тестових даних. Перший рядок містить одне ціле число $t$ ($1 \le t \le 10^5$) — кількість наборів тестових даних. Далі йде опис наборів тестових даних.

Перший рядок містить два цілі числа $n, m$ ($1 \le n, m \le 3000$, $1 \le \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 \le w_i \le 10^9$), що позначають ребро $(u_i, v_i)$ з вагою $w_i$.

Граф може бути незв'язним, а також містити петлі або кратні ребра.

Вихідні дані

Для кожного набору тестових даних виведіть $n$ рядків, кожен з яких містить рядок із $n$ символів, де $j$-й символ дорівнює $s_{i,j}$: 0, якщо трикутного шляху з $i$ до $j$ не існує, та 1 в іншому разі.

Приклади

Вхідні дані 1

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

Вихідні дані 1

1111
1111
1111
1111
11101110
11111111
11111111
01111000
11111000
11100111
11100111
01100111