Kamomeは現在、重み付き無向グラフ上の三角形パスについて研究しています。具体的には、あるパスが三角形であるとは、以下のいずれかを満たす場合を言います。

• そのパスの長さが 2 以下である、または
• そのパス上の任意の異なる 3 辺 $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$ で終わる三角形パスが存在するかどうかを判定する必要があります。各頂点からそれ自身への三角形パスは常に存在するものと仮定します。

図 1: 北京大学の「三角形」の一部

入力

各テストは複数のテストケースを含みます。最初の行には整数 $t$ ($1 \le t \le 10^5$) が含まれ、テストケースの数を示します。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、グラフの頂点数と辺数を示す 2 つの整数 $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$ を示す 3 つの整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$) が含まれます。

グラフは非連結であったり、重複した辺や多重辺を含むことがあります。

出力

各テストケースについて、$n$ 行を出力します。各行は $n$ 文字からなる文字列であり、$j$ 番目の文字は $s_{i,j}$ です。$s_{i,j}$ が '0' の場合は、$i$ から始まり $j$ で終わる三角形パスが存在しないことを意味し、そうでない場合は '1' です。

入出力例

入力 1

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

出力 1

1111
1111
1111
1111
11101110
11111111

入力 2

3 2
1 2 3
2 3 4
3 4 1

出力 2

01111000
11111000
11100111

入力 3

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

出力 3

11100111
01100111