小Yは想像力豊かな女の子です。

ある夜、小Yは満天の星空を見上げ、これまでに学んだ天文学の知識を使って、星座を一つずつ特定し始めました。しかし今回は、先人たちの知識に自分なりの創意工夫を加え、自分だけの星座模様を作りたいと考えました。

空には合計 $n$ 個の星があります。小Yは古今東西の様々な文献を調べ、合計 $m$ 個の情報を得ました。そのうち $i$ 番目の情報には、星 $a_i$ と星 $b_i$ の間に線を引くべきであると記されています。また、それぞれの情報に対して、年代や出典などの情報に基づき、その線に重み $c_i$ を与えました。

小Yは、これら $m$ 個の情報からいくつかを選び、その情報に基づいて星同士を繋ぎ、自分だけの模様を作ろうとしています。

小Yが望む模様には多重辺が含まれてはいけません。つまり、任意の2つの星の間には最大で1本の線しか引くことができません。また、この模様は連結である必要があります。

さらに、今年は2017年であるため、小Yは選んだ辺の重みの総和を $p = 17$ で割った余りが特定の数になることを望んでいます。そこで小Yは、$0 \le k < p$ のそれぞれについて、模様が連結であり、多重辺がなく、かつ辺の重みの総和を $p$ で割った余りが $k$ となるような組み合わせの数がいくつあるかを知りたいと考えています。

答えは非常に大きくなる可能性があるため、答えを $998244353$ で割った余りを求めてください。

入力形式

標準入力から以下の形式で入力が与えられます。

$n$ $m$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $\vdots$ $a_m$ $b_m$ $c_m$

出力形式

合計 $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

小課題

各テストケースのデータ規模および特徴は以下の表の通りです。

すべてのデータにおいて、$1 \le n \le 17, 1 \le m \le 10^5, 0 \le c_i < p = 17$ を満たします。