Đường đi ngắn nhất trên đồ thị mới

Cho đồ thị vô hướng có trọng số dạng cây gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $N-1$ cạnh. Gọi $D(i,j)$ là khoảng cách từ đỉnh $i$ đến đỉnh $j$ trên cây, tức tổng trọng số các cạnh trên đường đi từ $i$ đến $j$ (lưu ý đường đi từ đỉnh $i$ đến đỉnh $j$ chỉ thăm mỗi đỉnh duy nhất một lần). Trọng số các cạnh có thể âm.

Tạo đồ thị có hướng mới gồm $N$ đỉnh, với mỗi cặp đỉnh $(i,j)$ nếu $i<j$ thì thêm cạnh nối từ đỉnh $i$ đến đỉnh $j$ có trọng số là $D(i,j)$.

Yêu cầu: Hãy tìm đường đi ngắn nhất từ đỉnh $1$ đến tất cả các đỉnh trong đồ thị mới tạo.

Dữ liệu vào

• Dòng đầu gồm số nguyên $N$.
• Dòng thứ $i+1$ ($1\le i\le N-1$) gồm $3$ số nguyên $u_i,v_i,w_i$, với ý nghĩa có cạnh nối giữa $u_i$ và $v_i$ với trọng số $w_i$. Tất cả các cạnh này mô tả cây ban đầu.

Dữ liệu ra

In ra trên một dòng $N$ số nguyên cách nhau bởi dấu cách, số nguyên thứ $i$ là độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $i$ trên đồ thị mới (số thứ nhất luôn bằng $0$).

Ràng buộc

• $2\le N\le 8·{10}^4$.
• $1\le u_i<v_i\le N$, $|w_i|\le {10}^9$.
• Các cạnh đã cho tạo thành một cây.

Ví dụ