HSFZPC 2026 Problem C. Shiroi Album II Input file: Output file: Time limit: Memory limit: standard input standard output 6 seconds 1024 megabytes May 4th, 2026 Kamome is currently researching triangular paths on weighted undirected graphs. More specif- ically, a path is called triangular if and only if: • The length of this path is no more than 2, or • For any three different edges $e_1, e_2$, and $e_3$ on this path, it is always true that $w(e_1), w(e_2)$, and $w(e_3)$ can form the three sides of a triangle. Recall that positive integers $x, y$, and $z$ can form the sides of a triangle if and only if $x < y + z$, $y < z + x$, and $z < x + y$. Kamome has provided you with a weighted undirected graph. You need to determine for each pair of points $(u, v)$ whether there exists a triangular path starting from $u$ and ending at $v$. We assume that there is always a triangular path from each node to itself.

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

输入格式

Each test contains multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10^5$), indicating the number of test cases. The description of the test cases follows. The first line contains two integers $n, m$ ($1 \le n, m \le 3000$, $1 < \sum n^2, \sum m^2 \le 3000^2$), indicating the number of nodes and edges of this graph. The next $m$ lines, each line contains three integers $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $1 < w_i \le 10^9$), indicating edge $(u_i, v_i)$ with weight $w_i$. The graph is maybe disconnected or include self-loop or multiple edge.

输出格式

For each test case, output $n$ lines, each line contains a string of $n$ characters, where the $j$-th characters is $s_{i,j}$, if it is 0 indicating there is no triangular path start from $i$ and end at $j$, 1 otherwise.

样例

standard input

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

standard output

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