题目描述

Z-Kingdom 有着四通八达的现代化交通。时值独立庆典之际，随着来自周边国家旅客的日益增多，犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查，他们得到了一张地图，记载了 Z-Kingdom 内每一条道路的长度。

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

输入格式

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

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

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

输出格式

输出一行，包含 $\dfrac{N(N-1)}{2}$ 个整数 $C_{1,2},C_{1,3},\cdots,C_{1,N},C_{2,3},C_{2,4},\cdots,C_{2,N},\cdots,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\%$ 的数据，保证 $N \le 50$；
• 对于 $60\%$ 的数据，保证 $N \le 100$；
• 对于 $100\%$ 的数据，保证 $N \le 500$。