I like Dijkstra more than Bellman-Ford... But what should I do if I like BFS even more than Dijkstra?

Generally, in an undirected graph with weighted edges, the shortest path refers to the path with the minimum sum of edge weights. However, Jaewon, who loves BFS too much, wants to minimize the number of edges included in the path.

We define any path that minimizes the number of edges to be "Lemon Path". The weight of a Lemon Path is defined as the sum of the weights of the edges included in that path, and the "Lemon Distance" between two vertices is defined to be the average of the weights of all Lemon Paths connecting two vertices.

A connected graph with $N$ vertices and $M$ bidirectional edges is given. The $i$-th edge connects $U_i$ and $V_i$, and its weight is $C_i$.

Find the Lemon Distance between vertex $1$ and all other vertices. The graph may contain self-loops or multiple edges.

The input is given in the following format.

$N \ M$ $U_1 \ V_1 \ C_1$ $U_2 \ V_2 \ C_2$ $\vdots$ $U_M \ V_M \ C_M$

From the first line, print the Lemon Distance between vertex $1$ and vertex $i+1$ on the $i$-th line over $N-1$ lines, using the following method.

If the Lemon Distance is $\dfrac{p}{q}$ where $p$ and $q$ are coprime positive integers, print a positive integer $m$ such that $qm\equiv p \ (\mathrm{mod} \ 998 \ 244 \ 353)$ and $0\le m<998 \ 244 \ 353$. Also, it is guaranteed that the number of Lemon Paths between vertex $1$ and other vertex is never a multiple of $998 \ 244 \ 353$.

• $2 \le N \leq 100\ 000$.
• $1 \le M \leq 500\ 000$.
• $1 \leq U_i, V_i \leq N$ ($1 \leq i \leq M$).
• $0 \leq C_i < 998 \ 244 \ 353$ ($1 \leq i \leq M$).