Mạng truyền tin

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.

Yêu cầu: Với mỗi $r=1,2,\dots ,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ủ.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $N$ là số lượng máy tính ($1\le N\le {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\le u_i,v_i\le N$; $1\le w_i\le {10}^9$).

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

Dữ liệu ra

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$.

Ràng buộc

• $1\le N\le {10}^5$.
• $1\le u_i,v_i\le N$; $1\le w_i\le {10}^9$.
• Các dây cáp bảo đảm mọi máy tính liên thông với nhau.

Subtasks

• Subtask 1 ($16\%$ số điểm): $N\le 5000$.
• Subtask 2 ($12\%$ số điểm): $w_i\le 2$ và luôn có dây cáp nối giữa máy tính $i$ và máy tính $i+1$, $\forall i=1,2,\dots ,N-1$.
• Subtask 3 ($20\%$ số điểm): $w_i=1$, $\forall i=1,2,\dots ,N-1$.
• Subtask 4 ($16\%$ số điểm): $w_i\le 1000$, $\forall i=1,2,\dots ,N-1$.
• Subtask 5 ($16\%$ số điểm): Luôn có dây cáp nối giữa máy tính $i$ và máy tính $i+1$, $\forall i=1,2,\dots ,N-1$.
• Subtask 6 ($20\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ