#P17938. Shiroi Album II

Shiroi Album II

Shiroi Album II

给定一个带正整数边权的无向图。满足下列条件的路径称为三角路径:

  • 路径不超过两条边;或
  • 对路径上任意三条不同的边,它们的边权都能构成一个非退化三角形。

正整数 x,y,zx,y,z 能构成三角形,当且仅当 x<y+zx<y+z、y<z+xy<z+x、z<x+yz<x+y 同时成立。

请判断每一对顶点 (u,v)(u,v) 之间是否存在三角路径。规定每个顶点到自身总有三角路径。图可以不连通,可以有自环和重边。

输入格式

第一行是测试用例数 tt,1≤t≤1051\le t\le10^5。

每组用例第一行包含 n,mn,m,表示顶点数与边数。接下来 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,表示一条无向边及其边权。

  • 1≤n,m≤30001\le n,m\le3000;
  • 1≤ui,vi≤n1\le u_i,v_i\le n,1≤wi≤1091\le w_i\le10^9;
  • 一个输入文件内,∑n2≤30002\sum n^2\le3000^2,∑m2≤30002\sum m^2\le3000^2。

输出格式

每组用例输出 nn 行,每行恰好 nn 个字符。第 ii 行第 jj 个字符为 1 表示存在从 ii 到 jj 的三角路径,否则为 0。

样例 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
1111
1111
1111
1111
11101110
11111111
11111111
01111000
11111000
11100111
11100111
01100111