在 Byteland 有一个池塘，里面住着 $n$ 只海龟。池塘里还有 $n$ 座房子，编号从 $1$ 到 $n$。每座房子里恰好住着一只海龟。很快，一位来自 Bytemerica 的小龙虾移民将来到 Byteland。这只小龙虾非常善于社交，所有的海龟都是他的朋友。在访问期间，小龙虾计划住在其中一位朋友的家里。但问题是，他应该住在哪个房子里。

小龙虾移民对那些能让他访问尽可能多朋友的房子感兴趣。人们可能会认为访问朋友不是问题，但在 Byteland 的池塘里，这比看起来要困难。首先，为了访问某人，必须到达他的房子。其次，还必须返回。我们假设小龙虾移民不会访问他所居住的那座房子的海龟。

小龙虾的移动遵循以下规则：

• 在房子之间，小龙虾只能使用特定的路线移动。
• 每条路线都是单向的，连接两座不同的房子。连接相同房子的路线可能不止一条。
• 小龙虾可以正常移动或反向移动。当处于房子 $A$ 并正常移动时，如果存在从 $A$ 到 $B$ 的路线，小龙虾可以移动到房子 $B$。如果小龙虾正在反向移动，那么如果存在从 $B$ 到 $A$ 的路线，他就可以从 $A$ 移动到 $B$。
• 有些路线是特殊的。在使用此类路线后，小龙虾会改变他的移动方式——如果他之前是正常移动，那么他将开始反向移动；如果他之前是反向移动，那么他将开始正常移动。小龙虾不能在其他任何地方改变他的移动方式。
• 在迁徙开始时，小龙虾移民是反向移动的。在访问朋友时，小龙虾不会改变移动方式。在迁徙结束时，小龙虾必须处于反向移动状态（如果最后一条路线是特殊的，那么在进入这条路线之前，小龙虾必须处于正常移动状态）。

编写一个程序：

• 读取 Byteland 池塘中路线的描述，
• 对于每座房子，计算如果小龙虾住在该房子里，他可以访问的朋友数量，
• 将答案写入标准输出。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10\,000$, $1 \le m \le 100\,000$)。这些数字分别表示：房子的数量和路线的数量。接下来的 $m$ 行描述了具体的路线，每行一条。每条描述包含三个整数 $a$、$b$ 和 $s$ ($1 \le a, b \le n$, $s \in \{0, 1\}$)。整数 $a$ 表示起始房子的编号，$b$ 表示结束房子的编号。当且仅当 $s=1$ 时，该路线是特殊的。

输出格式

输出应包含 $n$ 行。第 $i$ 行应包含一个整数，表示如果小龙虾住在编号为 $i$ 的房子里，他可以访问的朋友数量。

样例

输入 1

5 5
2 1 1
2 3 0
3 4 0
4 2 0
5 3 1

输出 1

3
3
3
3
0

说明 1

住在 1 号房子时，小龙虾可以访问住在 2、3、4 号房子的朋友。住在 2 号房子时，小龙虾可以访问住在 3、4、5 号房子的朋友。住在 3 号房子时，小龙虾可以访问住在 2、4、5 号房子的朋友。住在 4 号房子时，小龙虾可以访问住在 2、3、5 号房子的朋友。住在 5 号房子时，他无法访问任何朋友。