문제

Kamome은 가중치 무방향 그래프에서 삼각형 경로를 연구하고 있습니다. 더 구체적으로, 경로는 다음과 같은 경우에만 삼각형 경로라고 합니다.

• 이 경로의 길이가 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$가 항상 참인 경우에만 해당합니다.

Kamome은 가중치 무방향 그래프를 제공했습니다. 각 쌍의 점 $(u, v)$에 대해 $u$에서 시작하여 $v$에서 끝나는 삼각형 경로가 존재하는지 결정해야 합니다. 모든 노드에서 자기 자신으로 가는 삼각형 경로가 항상 존재한다고 가정합니다.

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

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 10^5$)가 있습니다. 테스트 케이스 설명이 이어집니다.

첫 번째 줄에는 그래프의 노드 수와 간선 수를 나타내는 두 정수 $n, m$ ($1 \le n, m \le 3000$, $1 < \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 < w_i \le 10^9$)가 있으며, 이는 가중치 $w_i$를 갖는 간선 $(u_i, v_i)$를 나타냅니다.

그래프는 연결되지 않았거나 자기 루프 또는 다중 간선을 포함할 수 있습니다.

출력

각 테스트 케이스에 대해 $n$개의 줄을 출력합니다. 각 줄은 $n$개의 문자로 이루어진 문자열이며, 여기서 $j$번째 문자는 $s_{i,j}$입니다. $s_{i,j}$가 '0'이면 $i$에서 시작하여 $j$에서 끝나는 삼각형 경로가 없음을 나타내고, '1'이면 존재함을 나타냅니다.

예제

입력 1

2
4 3
1 2 2
1 3 2
2 3 2
3 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

제한

각 테스트 케이스에 대해 $1 \le t \le 10^5$. $1 \le n, m \le 3000$. $\sum n^2 \le 3000^2$. $\sum m^2 \le 3000^2$. $1 < w_i \le 10^9$.