Mô tả bài toán

Kamome hiện đang nghiên cứu các đường đi tam giác trên đồ thị vô hướng có trọng số. Cụ thể hơn, một đường đi được gọi là tam giác nếu và chỉ nếu: Độ dài của đường đi này không quá 2, hoặc Với bất kỳ ba cạnh khác nhau $e_1, e_2, e_3$ trên đường đi này, luôn đúng là $w(e_1), w(e_2), w(e_3)$ có thể tạo thành ba cạnh của một tam giác.

Nhắc lại rằng các số nguyên dương $x, y, z$ có thể tạo thành các cạnh của một tam giác nếu và chỉ nếu $x < y + z$, $y < z + x$, và $z < x + y$.

Kamome đã cung cấp cho bạn một đồ thị vô hướng có trọng số. Bạn cần xác định với mỗi cặp điểm $(u, v)$, liệu có tồn tại một đường đi tam giác bắt đầu từ $u$ và kết thúc tại $v$ hay không. Chúng ta giả định rằng luôn có một đường đi tam giác từ mỗi nút về chính nó.

Picture 1: A part of the "triangle" at Peking University

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^5$), cho biết số lượng trường hợp thử nghiệm. Tiếp theo là mô tả các trường hợp thử nghiệm.

Dòng đầu tiên chứa hai số nguyên $n, m$ ($1 \le n, m \le 3000$, $1 < \sum n^2, \sum m^2 \le 3000^2$), cho biết số lượng nút và cạnh của đồ thị. $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$), cho biết cạnh $(u_i, v_i)$ với trọng số $w_i$.

Đồ thị có thể bị rời rạc hoặc bao gồm các cạnh nối lặp hoặc đa cạnh.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, xuất ra $n$ dòng, mỗi dòng chứa một chuỗi gồm $n$ ký tự, trong đó ký tự thứ $j$ là $s_{i,j}$. Nếu $s_{i,j}$ là '0', nghĩa là không có đường đi tam giác nào bắt đầu từ $i$ và kết thúc tại $j$, ngược lại là '1'.

Ví dụ

Dữ liệu vào 1

2
4 3
1 2 2
1 2 2
2 3 2
3 2
1 2 3
2 3 2
3 4 3

Dữ liệu ra 1

1111
1111
1111
1111
11101110
11111111

Dữ liệu vào 2

3 2
1 2 3
2 3 4
3 4 1

Dữ liệu ra 2

01111000
11111000
11100111

Dữ liệu vào 3

2 6 2
1 2 6
6 7 4
6 8 5

Dữ liệu ra 3

11100111
01100111