题目描述

出题人很喜欢八重神子，于是最后决定送给你 $n$ 只狐狸作为礼物。

狐狸都很傲娇，因此 $n$ 只狐狸中只有 $m$ 对单向的交流渠道，一个交流渠道 $(u, v)$ 表示一只狐狸 $u$ 可以对另一只狐狸 $v$ 说话。

这些交流渠道又分为两种，一种需要花费 1 mora，一种则不需要。

当狐狸 $u$ 想要与狐狸 $v$ 说话时，狐狸 $u$ 需要把消息告诉与它有交流渠道的狐狸 $x_1$ ，$x_1$ 告诉狐狸 $x_2$ ，...，直到拥有通往狐狸 $v$ 的交流渠道的狐狸 $x_k$ 告诉狐狸 $v$ ，而狐狸 $u$ 需要为本次交流付出所有交流渠道的花费。

狐狸都十分聪明，因此它们都会选择花费最少的路径，这个路径集合称为 $(u, v)$ 的交流路径。

定义中间商次数为一只狐狸被所有有序狐狸对的交流路径集合（不存在交流路径则不考虑）覆盖的次数。

现在，你想要知道每只狐狸的中间商次数。

注意：

1. $(u, v)$ 和 $(v, u)$ 的交流路径不一定相同。
2. $(u, u)$ 的交流路径就是狐狸 $u$ 自身，这条路径给 $u$ 提供 $1$ 的中间商次数。
3. $(u, v)$ 的交流路径可能有多条，每一条都给其上的每只狐狸提供 $1$ 的中间商次数。
4. 可能存在不能达成交流的狐狸 $(u, v)$。
5. 保证不存在一个狐狸的集合，使得集合内的交流路径都是零花费。
6. $(u, v)$ 之间可能存在多条交流渠道。

本题答案最后对 998244353 取模

输入格式

第 $1$ 行共两个整数 $n, m$ ，表示狐狸的数量和交流渠道的数量。

第 $2\sim m+1$ 行，每行三个整数 $u, v, w$ ，表示从 $u$ 到 $v$ 有一条交流渠道，花费为 $w(w \in \{0, 1\})$。

输出格式

输出 $n$ 行，每行一个数，第 $i$ 行表示编号为 $i$ 的狐狸的中间商次数。

测试用例

样例输入

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

样例输出

5
12
7
8
11

数据范围

对于前 $10\%$ 的数据, $n \le 10$;

对于前 $20\%$ 的数据, $n \le 100$;

对于前 $40\%$ 的数据, $n \le 1000, m \le 5000$;

对于另 $20\%$ 的数据，没有零花费的交流渠道;

对于 $100\%$ 的数据, $1 \le n \le 1000, 1 \le m \le 50000, w \in \{0, 1\}$，保证不存在一个狐狸的集合，使得集合内的交流路径都是零花费。