F. Candy Machine
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has a candy machine, which can be represented as a tree of size $$$n$$$. The nodes are labelled $$$1, 2, \dots, n$$$, and rooted at node $$$1$$$. Node $$$u$$$ initially contains the candy labelled $$$u$$$. If $$$u$$$ is a non-leaf node (a node with one or more children), then it starts with exactly one candy of type $$$u$$$; otherwise, it starts with an infinite number of candies.

She can spend $$$1$$$ dollar to get the candy at the root, making the root empty. Afterwards, a candy from one of its children is dropped into the node. The candy that drops is chosen with probability according to the weight of the edge. This creates a new empty node, and the process continues until there are no more empty nodes.

More formally, if node $$$u$$$ is empty and has children $$$v_1, v_2, \ldots, v_k$$$ with associated costs $$$w_1, w_2, \ldots, w_k$$$, then the probability of getting a candy from node $$$v_i$$$ is $$$\frac{w_i}{\sum w}$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, calculate the expected amount of money she has to spend in order to get a candy of type $$$i$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$), the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the size of the candy machine.

The next $$$n-1$$$ lines contain three integers $$$u, v, w$$$ ($$$1\leq u,v\leq n$$$, $$$1\leq w\leq 10^9$$$) — the endpoints and weight of each edge. It is guaranteed that the edges form a tree.

The sum of $$$n$$$ over all test cases will not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output one line with $$$n$$$ integers, where the $$$i$$$-th integer is the expected amount of money she needs to spend to get a candy of type $$$i$$$. Output the answer modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Example
Input
3
2
1 2 5
5
1 2 10
1 3 9
2 4 7
2 5 6
12
1 2 5
1 3 4
2 4 9
1 5 13
5 6 12
3 7 9
3 8 6
7 9 1
8 10 2
3 11 17
2 12 6
Output
1 2
1 698771050 443664160 570425351 715408460
1 199648876 499122183 532397001 153576057 307152113 720954281 831870330 942786379 166374124 146800657 199648887
Note

In the first test case, candy $$$1$$$ will fall out in $$$1$$$ drop, and in the next candy $$$2$$$ is guaranteed to fall out.

In the second test case, candy $$$1$$$ will once again fall out in $$$1$$$ drop. The expected drops is $$$\frac{29}{10}$$$ for candy $$$2$$$ and $$$\frac{28}{9}$$$ for candy $$$3$$$.