קאמומה חוקר כעת מסלולים משולשיים בגרפים לא מכוונים ממושקלים. באופן ספציפי יותר, מסלול נקרא משולשי אם ורק אם:

• אורכו של מסלול זה אינו עולה על $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