题目描述

机器人警察得到了一张地图，记载了区内每一条道路的长度。

显然，为了减少犯罪行为被发现的可能性，犯罪分子总是会选择最短的路径来行动。为 了方便安排人手和推测犯罪分子采取的路线，他们希望得知任意两个地点之间，有多少条犯 罪分子可能会选择的道路。

输入格式

第一行，包含两个整数 $N, M，$表示 区内的地点数和道路数。

接下来 $M$ 行，每行包含三个整数 $xi, yi, li$，表示道路连接的两个不同地点的标号，以及 道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

输出格式

输出一行，包含 $N(N - 1)/2$ 个整数 $ C_{1,2} , C_{1,3} , . . . , C_{1,N} , C_{2,3} , C_{2,4} , . . . , C_{2,N} , . . . , C_{N-1,N}$。

其中 $C_{x,y}$ 表示 $x$ 号地点到 $y$ 号地点之间有多少条犯罪分子可能会选择的道路。

5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4

1 4 1 2 1 5 6 1 2 1

数据规模与约定

• 对于分值为 $30$ 的子任务 $1$，保证 $N ≤ 50$

• 对于分值为 $30$ 的子任务 $2$，保证 $N ≤ 100$

• 对于分值为 $40$ 的子任务 $3$，保证 $N ≤ 500$。