Một mạng truyền tin có ~N~ máy tính, các máy tính được đánh số từ ~1~ đến ~N~. Có ~N - 1~ dây cáp, được đánh số từ ~1~ đến ~N - 1~. Dây cáp thứ ~i~ nối máy tính ~u_i~ với máy tính ~v_i~ và có giới hạn truyền tải ~w_i~. Các dây cáp bảo đảm từ một máy tính bất kì có thể truyền tin đến tất cả các máy tính còn lại theo dây cáp trực tiếp giữa chúng hoặc thông qua đường truyền tin đi qua một số máy tính và dây cáp nào đó. Khi hai máy tính truyền tin cho nhau, chúng sẽ luôn sử dụng đường truyền tin sao cho không sử dụng dây cáp nào quá một lần. Độ lớn của gói tin truyền đi phải không lớn hơn giới hạn truyền tải của mọi dây cáp mà nó sử dụng. Chi phí để truyền một gói tin giữa hai máy tính bằng kích thước của gói tin nhân với bình phương số lượng dây cáp trên đường truyền tin.

Người ta muốn chọn ra một máy tính ~r~ để làm máy chủ. Khi đó, máy tính ~r~ sẽ truyền tin đến tất cả các máy tính khác. Vì phải dự trù cho mọi trường hợp, ta cần phải xét chi phí truyền tin tối đa. Chi phí truyền tin tối đa giữa máy tính ~r~ và máy tính ~x~ là ~C_{min}(r, x) \times (D(r, x))^2~ với ~C_{min}(r, x)~ là giới hạn truyền tải nhỏ nhất trong số các giới hạn truyền tải của các dây cáp trên đường truyền tin giữa máy tính ~r~ và máy tính ~x~, ~D(r, x)~ là số dây cáp trên đường truyền tin giữa máy tính ~r~ và máy tính ~x~. Chi phí vận hành mạng là tổng của chi phí truyền tin tối đa giữa máy tính ~r~ và tất cả các máy tính khác.

~\textbf{Yêu cầu}~: Với mỗi ~r = 1, 2, \ldots, N~, hãy tính chi phí vận hành mạng nếu chọn máy tính ~r~ làm máy chủ.

Input

Vào từ file văn bản ~\texttt{NETW.INP}~:

• Dòng đầu chứa một số nguyên ~N~ là số lượng máy tính ~(1 \leq N \leq 10^5)~.

• Dòng thứ ~i~ trong số ~N - 1~ dòng tiếp theo chứa ba số nguyên ~u_i, v_i~ và ~w_i~ cho biết có một dây cáp nối máy tính ~u_i~ với máy tính ~v_i~ và có giới hạn truyền tải là ~w_i~ ~(1 \leq u_i, v_i \leq N; 1 \leq w_i \leq 10^9)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản ~\texttt{NETW.OUT}~:

• Gòm ~N~ dòng, trong đó dòng thứ ~r~ chứa một số nguyên là phần dử của chi phí vận hành mạng nếu chọn máy tính ~r~ làm máy chủ trong phép chia cho ~998244353~.

Scoring

Sample Input 1

7
1 2 3
1 3 2
2 4 2
2 6 1
4 5 1
4 7 2

Sample Output 1

44
26
85
35
43
36
73