Kamome obecnie bada ścieżki trójkątne w ważonym grafie nieskierowanym. Konkretnie, ścieżka jest trójkątna, jeśli spełnia jeden z poniższych warunków:

• Długość ścieżki wynosi co najwyżej 2, lub
• Dla dowolnych trzech różnych krawędzi $e_1, e_2, e_3$ na tej ścieżce, $w(e_1), w(e_2), w(e_3)$ zawsze mogą być bokami trójkąta.

Przypomnijmy, że dodatnie liczby całkowite $x, y, z$ mogą być bokami trójkąta wtedy i tylko wtedy, gdy $x < y + z$, $y < z + x$ oraz $z < x + y$.

Kamome daje Ci ważony graf nieskierowany. Dla każdej pary wierzchołków $(u, v)$ musisz stwierdzić, czy istnieje ścieżka trójkątna zaczynająca się w $u$ i kończąca w $v$. Zakładamy, że ścieżka trójkątna z każdego wierzchołka do niego samego zawsze istnieje.

Rysunek 1: Część „trójkąta” Uniwersytetu Pekińskiego

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^5$) oznaczającą liczbę przypadków. Następnie następują opisy kolejnych przypadków.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n, m$ ($1 \le n, m \le 3000$, $1 < \sum n^2, \sum m^2 \le 3000^2$) oznaczające liczbę wierzchołków i krawędzi grafu.

Kolejne $m$ wierszy zawiera po trzy liczby całkowite $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$) opisujące krawędź $(u_i, v_i)$ i jej wagę $w_i$.

Graf może być niespójny, zawierać powtarzające się krawędzie lub wielokrawędzie.

Wyjście

Dla każdego przypadku testowego wypisz $n$ wierszy. Każdy wiersz jest ciągiem $n$ znaków, gdzie $j$-ty znak to $s_{i,j}$. Jeśli $s_{i,j}$ jest '0', oznacza to, że nie istnieje ścieżka trójkątna z $i$ do $j$; w przeciwnym przypadku jest '1'.

Przykład

Wejście 1

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

Wyjście 1

1111
1111
1111
1111
11101110
11111111

Wejście 2

3 2
1 2 3
2 3 4
3 4 1

Wyjście 2

01111000
11111000
11100111

Wejście 3

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

Wyjście 3

11100111
01100111