Kamome er núna að rannsaka þríhyrningsvegi á vigtuðum óstefndum netum. Nánar tiltekið kallast vegur þríhyrningsvegur ef og aðeins ef:

• Lengd þessa vegar er ekki meiri en $2$, eða
• Fyrir hvaða þrjá ólíka leggi $e_1$, $e_2$ og $e_3$ sem er á þessum vegi gildir alltaf að $w(e_1)$, $w(e_2)$ og $w(e_3)$ geta myndað þrjár hliðar þríhyrnings.

Mundu að jákvæðar heiltölur $x$, $y$ og $z$ geta myndað hliðar þríhyrnings ef og aðeins ef $x < y + z$, $y < z + x$ og $z < x + y$.

Kamome hefur látið þig fá vigtað óstefnt net. Þú þarft að ákvarða fyrir hvert par af hnútum $(u, v)$ hvort til sé þríhyrningsvegur sem byrjar í $u$ og endar í $v$. Við gerum ráð fyrir að alltaf sé til þríhyrningsvegur frá hverjum hnúti til sjálfs sín.

Inntak

Hvert próf inniheldur mörg prófunartilvik. Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 10^5$), sem gefur til kynna fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir á eftir.

Fyrsta línan inniheldur tvær heiltölur $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), sem gefa til kynna fjölda hnúta og leggja í þessu neti.

Næstu $m$ línur innihalda hver um sig þrjár heiltölur $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), sem tákna legg $(u_i, v_i)$ með vigt $w_i$.

Netið getur verið ósamanhangandi eða innihaldið sjálfslykkjur eða margfalda leggi.

Úttak

Fyrir hvert prófunartilvik skal prenta út $n$ línur, þar sem hver lína inniheldur streng af $n$ stöfum, þar sem $j$-ti stafurinn er $s_{i,j}$: 0 ef enginn þríhyrningsvegur er til sem byrjar í $i$ og endar í $j$, en 1 annars.

Dæmi

Inntak 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

Úttak 1

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