Baiyun has embarked on a journey.

There are $n$ cities in total, numbered from $1$ to $n$, with some roads connecting them. The road structure can be abstracted as a cactus graph. An undirected connected graph is called a cactus if every edge belongs to at most one simple cycle. A simple cycle is a cycle that does not visit any node more than once.

Baiyun has a preference value for each road between these cities. The preference value of a path is the product of the preference values of all roads on that path.

Now, Baiyun is preparing to depart from city $1$. To plan a reasonable route, Baiyun occasionally asks Baitu: "What is the sum of the preference values of all paths from city $1$ to city $k$ that do not traverse the same road twice?"

This has stumped Baitu. Please help calculate the corresponding answer for $k=1, 2, \ldots, n$. You only need to output the answer modulo $998244353$ ($= 7 \times 17 \times 2^{23} + 1$, a prime number).

Input

The first line contains two positive integers $n$ and $m$, representing the number of cities and the number of roads. It is guaranteed that $n \ge 2$.

Each of the next $m$ lines contains three positive integers $v, u, w$ ($1 \le v, u \le n, 1 \le w < 998244353$), representing a road connecting city $v$ and $u$ with a preference value of $w$.

It is guaranteed that the input graph is a cactus, has no self-loops, but may contain multiple edges.

Output

Output $n$ lines, where the $i$-th line contains an integer representing the answer for $k=i$.

Examples

Input 1

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

Output 1

3
2
2
2
2
2
20
40
60
80
100

Note 1

Note that two paths are considered different if they consist of a different sequence of edges, or if there exists an $x$ such that $1 \le x \le \text{path length}$ where the $x$-th edge traversed by the two paths is different.

A path of length $0$ is also a valid path, and its weight is considered to be $1$.

Subtasks

For all data, $n \le 10^5, 1 \le w < 998244353$.

Although the range for $m$ is not explicitly given, those familiar with cactus graphs know that for a cactus, it must satisfy $n-1 \le m \le 2n-2$.