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$ 結束嘅三角形路徑。我哋假設由每個節點去佢自己總係存在一條三角形路徑。

輸入格式

每個測試包含多組測試數據。第一行包含一個整數 $t$（$1 \le t \le 10^5$），表示測試數據嘅組數。接落嚟係測試數據嘅描述。

第一行包含兩個整數 $n, m$（$1 \le n, m \le 3000$，$1 \le \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 \le w_i \le 10^9$），表示權值為 $w_i$ 嘅邊 $(u_i, v_i)$。

個圖可能唔連通，或者包含自環或者重邊。

輸出格式

對於每組測試數據，輸出 $n$ 行，每行包含一個由 $n$ 個字符組成嘅字符串，其中第 $j$ 個字符為 $s_{i,j}$：如果唔存在由 $i$ 出發並喺 $j$ 結束嘅三角形路徑則為 0，否則為 1。

樣例

輸入 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

輸出 1

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