Kamome erforscht derzeit Dreieckspfade auf gewichteten ungerichteten Graphen. Genauer gesagt heißt ein Pfad Dreieckspfad, genau dann, wenn:

• die Länge dieses Pfades höchstens $2$ beträgt, oder
• für beliebige drei verschiedene Kanten $e_1$, $e_2$ und $e_3$ auf diesem Pfad stets gilt, dass $w(e_1)$, $w(e_2)$ und $w(e_3)$ die drei Seiten eines Dreiecks bilden können.

Zur Erinnerung: Positive ganze Zahlen $x$, $y$ und $z$ können genau dann die Seiten eines Dreiecks bilden, wenn $x < y + z$, $y < z + x$ und $z < x + y$ gilt.

Kamome hat dir einen gewichteten ungerichteten Graphen gegeben. Du musst für jedes Punktepaar $(u, v)$ bestimmen, ob es einen Dreieckspfad gibt, der bei $u$ beginnt und bei $v$ endet. Wir nehmen an, dass es von jedem Knoten zu sich selbst immer einen Dreieckspfad gibt.

Eingabe

Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $t$ ($1 \le t \le 10^5$), die die Anzahl der Testfälle angibt. Es folgt die Beschreibung der Testfälle.

Die erste Zeile enthält zwei ganze Zahlen $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), die die Anzahl der Knoten und Kanten dieses Graphen angeben.

Die nächsten $m$ Zeilen enthalten jeweils drei ganze Zahlen $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), die eine Kante $(u_i, v_i)$ mit dem Gewicht $w_i$ angeben.

Der Graph ist möglicherweise nicht zusammenhängend oder enthält Schleifen oder Mehrfachkanten.

Ausgabe

Gib für jeden Testfall $n$ Zeilen aus, von denen jede eine Zeichenkette aus $n$ Zeichen enthält, wobei das $j$-te Zeichen $s_{i,j}$ ist: 0, falls es keinen Dreieckspfad gibt, der bei $i$ beginnt und bei $j$ endet, und andernfalls 1.

Beispiele

Eingabe 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

Ausgabe 1

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