ขณะนี้ 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$) แทนเส้นเชื่อม $(u_i, v_i)$ ที่มีน้ำหนัก $w_i$

กราฟนี้อาจ ไม่เชื่อมโยงกัน หรืออาจมี วงวนในตัวเอง (self-loop) หรือ เส้นเชื่อมซ้ำ (multiple edges)

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบย่อย ให้แสดงผล $n$ บรรทัด แต่ละบรรทัดประกอบด้วยสตริงความยาว $n$ อักขระ โดยที่อักขระตัวที่ $j$ คือ $s_{i,j}$: เป็น 0 หากไม่มีวิถีสามเหลี่ยมที่เริ่มต้นจาก $i$ และสิ้นสุดที่ $j$ และเป็น 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