小 Y 是一个富有想象力的女孩子。

一天夜里，小 Y 望着满天的星辰，开始用自己之前学到的天文知识，逐个辨认星座。不过这次，她希望在前人的基础上添加些自己的创意，从而得到属于自己的图案。

天空中共有 $n$ 颗星星。小 Y 通过翻阅古今中外的各种典籍，得到了 $m$ 段资料。其中，第 $i$ 段资料说星星 $a_i$ 和星星 $b_i$ 之间应该有一条连线。对于每段资料，小 Y 还根据它的年代、出处等信息，给了这条连线一个权值 $c_i$。

小 Y 想从这 $m$ 段资料中选出一些，根据其中的信息将星星连接起来，作为自己的图案。

小 Y 希望这样得到的图案中没有重边，也就是说任意两颗星星之间至多有一条边。并且这个图案应该是连通的。

除此之外，由于今年是 2017 年，小 Y 希望她选出边的权值和对 $p = 17$ 取模的结果为某个特定的数。于是小 Y 想知道，对于 $0 \le k < p$ 中的每一个 $k$，满足图案连通，无重边并且边权和对 $p$ 取模的结果为 $k$ 的方案数是多少？

由于答案可能很大，你只需要告诉小 Y 答案对 $998244353$ 取模的结果。

输入格式

从标准输入读入数据。

第一行有两个整数 $n, m$，含义如题述。

接下来 $m$ 行，每行三个整数 $a_i, b_i, c_i$，表示有一条连接 $a_i$ 和 $b_i$ 的，权值为 $c_i$ 的边。

输出格式

输出到标准输出。

输出共 $p$ 行，每行一个整数，第 $i$ 表示边权和模 $p$ 为 $i - 1$ 的方案数对 $998244353$ 取模的结果。

样例数据

样例输入

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

样例输出

5
12
13
11
6
1
0
0
0
0
0
0
0
0
0
0
0

子任务

每个测试点的数据规模及特点如下表所示。

对于 100% 的数据，保证 $1 \le n \le 17, 1 \le m \le 10^5, 0 \le c_i < p = 17$。