小 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$ 取模的結果。

範例

範例輸入 1

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

範例輸出 1

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$。