Kamome saat ini sedang meneliti lintasan segitiga pada graf tak berarah berbobot. Lebih spesifiknya, sebuah lintasan disebut segitiga jika dan hanya jika:

• Panjang lintasan ini tidak lebih dari $2$, atau
• Untuk setiap tiga sisi berbeda $e_1$, $e_2$, dan $e_3$ pada lintasan ini, selalu berlaku bahwa $w(e_1)$, $w(e_2)$, dan $w(e_3)$ dapat membentuk ketiga sisi dari sebuah segitiga.

Ingat kembali bahwa bilangan bulat positif $x$, $y$, dan $z$ dapat membentuk sisi-sisi sebuah segitiga jika dan hanya jika $x < y + z$, $y < z + x$, dan $z < x + y$.

Kamome telah memberikan sebuah graf tak berarah berbobot kepada Anda. Anda perlu menentukan untuk setiap pasangan titik $(u, v)$ apakah terdapat lintasan segitiga yang dimulai dari $u$ dan berakhir di $v$. Kita mengasumsikan bahwa selalu terdapat lintasan segitiga dari setiap simpul ke dirinya sendiri.

Format Masukan

Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi satu bilangan bulat $t$ ($1 \le t \le 10^5$), yang menyatakan banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama berisi dua bilangan bulat $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), yang menyatakan banyaknya simpul dan sisi dari graf ini.

$m$ baris berikutnya masing-masing berisi tiga bilangan bulat $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), yang menyatakan sisi $(u_i, v_i)$ dengan bobot $w_i$.

Graf tersebut mungkin tidak terhubung atau memiliki gelung (self-loop) maupun sisi ganda (multiple edges).

Format Keluaran

Untuk setiap kasus uji, keluarkan $n$ baris, masing-masing berisi sebuah string yang terdiri dari $n$ karakter, dengan karakter ke-$j$ adalah $s_{i,j}$: bernilai 0 jika tidak ada lintasan segitiga yang dimulai dari $i$ dan berakhir di $j$, dan 1 jika sebaliknya.

Contoh

Masukan 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

Keluaran 1

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