白云开始了一段旅程。

旅途中一共有 $n$ 个城市，编号为 $1$ 到 $n$，城市之间有一些道路相连。其道路结构可以抽象为一棵仙人掌。如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

白云对这些城市间的每条道路都有一个喜爱度。一条路径的喜爱度是其上所有道路的喜爱度的乘积。

现在白云在 $1$ 号城市准备出发。为了制定合理的路线，白云会时不时问白兔：“从 $1$ 号城市出发不经过重复道路到达 $k$ 号城市的所有路径喜爱度之和是多少？”

这可难倒了白兔，请你帮忙对于 $k=1,2,\ldots,n$ 求出相应答案。只需要输出答案对$998244353( = 7\times 17\times 2^{23}+1,$一个质数$)$取模后的值。

输入格式

第 $1$ 行两个正整数 $n,m$ 表示城市的个数和道路的条数。保证 $n \ge 2$。

接下来 $m$ 行每行两个正整数 $v,u,w(1 \le v,u \le n,1 \le w < 998244353)$ 表示一条连接城市 $v$ 和 $u$ 的喜爱度为 $w$ 的道路。

保证输入的图是一棵仙人掌，没有自环，但可能有重边。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数表示 $k=i$ 时的答案。

样例数据

样例输入

11 11
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
2 7 10
3 8 20
4 9 30
5 10 40
6 11 50

样例输出

3
2
2
2
2
2
20
40
60
80
100

样例解释

注意，两条路径不同为它们经过的边数不同或存在一个满足 $1 \le x \le$ 路径长度 的 $x$ 使得这两条路径经过的第 $x$ 条边不同。

长度为$0$的路径也是合法路径，权值视为 $1$。

子任务

对于所有数据，$n \le 10^5,1 \le w < 998244353$。

虽然我没有给 $m$ 的范围，但是熟悉仙人掌的小朋友都知道对于仙人掌肯定满足 $n-1 \le m \le 2n-2$。