Kamome étudie actuellement les chemins triangulaires dans des graphes non orientés pondérés. Plus précisément, un chemin est dit triangulaire si et seulement si : La longueur de ce chemin n'excède pas 2, ou Pour toute paire de trois arêtes distinctes $e_1, e_2, e_3$ sur ce chemin, il est toujours vrai que $w(e_1), w(e_2)$ et $w(e_3)$ peuvent former les trois côtés d'un triangle.

Rappelons que trois entiers positifs $x, y, z$ peuvent former les côtés d'un triangle si et seulement si $x < y + z$, $y < z + x$ et $z < x + y$.

Kamome vous a fourni un graphe non orienté pondéré. Vous devez déterminer pour chaque paire de points $(u, v)$ s'il existe un chemin triangulaire partant de $u$ et se terminant en $v$. Nous supposons qu'il existe toujours un chemin triangulaire de chaque nœud vers lui-même.

Picture 1: A part of the "triangle" at Peking University

Entrée

Chaque cas de test contient plusieurs cas de test. La première ligne contient un entier $t$ ($1 \le t \le 10^5$), indiquant le nombre de cas de test. La description des cas de test suit.

La première ligne contient deux entiers $n, m$ ($1 \le n, m \le 3000$, $1 < \sum n^2, \sum m^2 \le 3000^2$), indiquant le nombre de nœuds et d'arêtes de ce graphe.

Les $m$ lignes suivantes, chaque ligne contient trois entiers $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$), indiquant l'arête $(u_i, v_i)$ avec le poids $w_i$.

Le graphe peut être déconnecté ou inclure des auto-boucles ou des arêtes multiples.

Sortie

Pour chaque cas de test, affichez $n$ lignes, chaque ligne contenant une chaîne de $n$ caractères, où le $j$-ième caractère est $s_{i,j}$. Si c'est 0, cela indique qu'il n'y a pas de chemin triangulaire partant de $i$ et se terminant en $j$, sinon c'est 1.

Exemples

Entrée 1

4
3
1 2 2
2 3 2
3 4 3

Sortie 1

1111
1111
1111
1111

Entrée 2

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

Sortie 2

11101110
11111111
01111000
11111000
11100111
11100111
01100111