يبحث كامومي حاليًا في المسارات المثلثية في الرسوم البيانية غير الموجهة الموزونة. وبشكل أكثر تحديدًا، يُسمى المسار مثلثيًا إذا وفقط إذا:

• كان طول هذا المسار لا يزيد عن $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$.

قدّم لك كامومي رسمًا بيانيًا غير موجه وموزونًا. تحتاج إلى تحديد ما إذا كان يوجد مسار مثلثي يبدأ من $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$.

قد يكون الرسم البياني غير متصل أو يحتوي على حلقات ذاتية أو أضلاع متعددة.

الإخراج

لكل حالة اختبار، اطبع $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