题目描述

有一个神奇的图，对于一个 $X$ 点可以延伸出 $Z$ 个点；

定义可以延伸的点$Y$满足以下条件：

1. 与$X$点联通
2. 从$X$点到$Y$点的路径边权值相同的点（只要一条路径满足即可）
3. $Y \ne X$

请问你能求出 $X$ 点最多能延伸出的点吗？

输入格式

第一行，两个整数 $N,M$，表示有 $N$ 个点 $M$ 条边；

接下来的 $M$ 行，每行三个整数 $X_i,Y_i,D_i$，表示第 $i$ 个边的两个顶点和权值；

输出格式

输出 $N$ 个数，表示第 $i$ 个点最多可以延伸的点的个数；

2 1
1 2 1

1
1

提示

$1 \le N \le 10^3$

$1 \le M \le 10^5$

$1 \le D_i \le 10^9$

$1 \le X_i,Y_i \le N$