Kamome tutkii parhaillaan kolmiopolkuja painotetuissa suuntaamattomissa verkoissa. Tarkemmin sanottuna polkua kutsutaan kolmiopoluksi jos ja vain jos:

• Tämän polun pituus on enintään $2$, tai
• Mille tahansa kolmelle eri kaarelle $e_1$, $e_2$ ja $e_3$ tällä polulla pätee aina, että $w(e_1)$, $w(e_2)$ ja $w(e_3)$ voivat muodostaa kolmion kolme sivua.

Muista, että positiiviset kokonaisluvut $x$, $y$ ja $z$ voivat muodostaa kolmion sivut jos ja vain jos $x < y + z$, $y < z + x$ ja $z < x + y$.

Kamome on antanut sinulle painotetun suuntaamattoman verkon. Sinun tulee selvittää jokaiselle solmuparille $(u, v)$, onko olemassa kolmiopolkua, joka alkaa solmusta $u$ ja päättyy solmuun $v$. Oletamme, että jokaisesta solmusta itseensä on aina olemassa kolmiopolku.

Syöte

Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 10^5$), joka ilmoittaa testitapausten lukumäärän. Seuraavaksi on testitapausten kuvaus.

Ensimmäinen rivi sisältää kaksi kokonaislukua $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), jotka ilmoittavat tämän verkon solmujen ja kaarien lukumäärän.

Seuraavat $m$ riviä sisältävät kukin kolme kokonaislukua $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), jotka ilmoittavat kaaren $(u_i, v_i)$, jonka paino on $w_i$.

Verkko voi olla epäyhtenäinen tai sisältää silmukoita (self-loops) tai moninkertaisia kaaria.

Tuloste

Tulosta jokaista testitapausta kohden $n$ riviä, joista jokainen sisältää $n$ merkin pituisen merkkijonon, missä $j$. merkki on $s_{i,j}$: 0, jos solmusta $i$ alkavaa ja solmuun $j$ päättyvää kolmiopolkua ei ole olemassa, ja muuten 1.

Esimerkit

Syöte 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

Tuloste 1

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