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