Kamome forsker for tiden på triangulære stier i vektede urettede grafer. Mer spesifikt kalles en sti triangulær hvis og bare hvis:

• Lengden på denne stien ikke er mer enn $2$, eller
• For enhver tre forskjellige kanter $e_1$, $e_2$ og $e_3$ på denne stien gjelder det alltid at $w(e_1)$, $w(e_2)$ og $w(e_3)$ kan danne de tre sidene i en trekant.

Husk at positive heltall $x$, $y$ og $z$ kan danne sidene i en trekant hvis og bare hvis $x < y + z$, $y < z + x$ og $z < x + y$.

Kamome har gitt deg en vektet urettet graf. Du må avgjøre for hvert par av noder $(u, v)$ om det finnes en triangulær sti som starter i $u$ og slutter i $v$. Vi antar at det alltid finnes en triangulær sti fra hver node til seg selv.

Inndata

Hver test inneholder flere testtilfeller. Den første linjen inneholder ett heltall $t$ ($1 \le t \le 10^5$), som angir antall testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen inneholder to heltall $n, m$ ($1 \le n, m \le 3000$, $1 \le \sum n^2, \sum m^2 \le 3000^2$), som angir antall noder og kanter i denne grafen.

De neste $m$ linjene inneholder hver tre heltall $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$), som angir en kant $(u_i, v_i)$ med vekt $w_i$.

Grafen kan være usammenhengende eller inneholde egensløyfer (self-loops) eller multiple kanter.

Utdata

For hvert testtilfelle skal du skrive ut $n$ linjer, der hver linje inneholder en streng med $n$ tegn, hvor det $j$-te tegnet er $s_{i,j}$: 0 hvis det ikke finnes noen triangulær sti som starter i $i$ og slutter i $j$, og 1 ellers.

Eksempler

Inndata 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

Utdata 1

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