#B0005. 图的延伸

图的延伸

题目描述

有一个神奇的图,对于一个 XX 点可以延伸出 ZZ 个点;

定义可以延伸的点YY满足以下条件:

  1. XX点联通
  2. XX点到YY点的路径边权值相同的点(只要一条路径满足即可)
  3. YXY \ne X

请问你能求出 XX 点最多能延伸出的点吗?

输入格式

第一行,两个整数 N,MN,M,表示有 NN 个点 MM 条边;

接下来的 MM 行,每行三个整数 Xi,Yi,DiX_i,Y_i,D_i,表示第 ii 个边的两个顶点和权值;

输出格式

输出 NN 个数,表示第 ii 个点最多可以延伸的点的个数;

2 1
1 2 1
1
1

提示

1N1031 \le N \le 10^3

1M1051 \le M \le 10^5

1Di1091 \le D_i \le 10^9

1Xi,YiN1 \le X_i,Y_i \le N