Descripción

Kamome está investigando actualmente caminos triangulares en grafos no dirigidos ponderados. Más específicamente, un camino se llama triangular si y solo si: La longitud de este camino no es más de 2, o Para cualquier tres aristas diferentes $e_1, e_2, e_3$ en este camino, siempre se cumple que $w(e_1), w(e_2), w(e_3)$ pueden formar los tres lados de un triángulo.

Recuerda que los enteros positivos $x, y, z$ pueden formar los lados de un triángulo si y solo si $x < y + z$, $y < z + x$, y $z < x + y$.

Kamome te ha proporcionado un grafo no dirigido ponderado. Debes determinar para cada par de puntos $(u, v)$ si existe un camino triangular que comience en $u$ y termine en $v$. Asumimos que siempre existe un camino triangular de cada nodo a sí mismo.

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

Entrada

Cada caso de prueba contiene múltiples casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 10^5$), que indica el número de casos de prueba. La descripción de los casos de prueba sigue.

La primera línea contiene dos enteros $n, m$ ($1 \le n, m \le 3000$, $1 < \sum n^2, \sum m^2 \le 3000^2$), que indican el número de nodos y aristas de este grafo.

Las siguientes $m$ líneas, cada línea contiene tres enteros $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$), que indican la arista $(u_i, v_i)$ con peso $w_i$.

El grafo puede estar desconectado o incluir auto-bucles o aristas múltiples.

Salida

Para cada caso de prueba, se imprimen $n$ líneas, cada línea contiene una cadena de $n$ caracteres, donde el $j$-ésimo carácter es $s_{i,j}$. Si es '0' indica que no hay un camino triangular desde $i$ hasta $j$, y '1' en caso contrario.

Ejemplos

Entrada 1

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

Salida 1

1111
1111
1111
11101110
11111111
11111111
01111000
11111000

Entrada 2

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

Salida 2

11100111
11100111
01100111
01100111