Cho đồ thị có trọng số gồm \(N\) đỉnh 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. (Lưu ý đường đi từ đỉnh \(i\) đến đỉnh \(j\) chỉ thăm mỗi đỉnh duy nhất một lần)

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)\).

Nhiệm vụ của bạn là hãy tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh khác trong đồ thị mới tạo. 

Dữ liệu vào: 

- Dòng đầu gồm số nguyên \(N\) \((2 ≤ N ≤ 8 \times 10^4 )\).

- Dòng thứ \(i + 1\) \((1 ≤ i ≤ N - 1)\) bao gồm 3 số nguyên: \(u_i, v_i, w_i\) \((1 \leq u_i \le v_i \le N, \left| w_i \right| \leq 10^9 )\), 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.

Kết quả:

- Gồm \(N\) số nguyên, số nguyên thứ \(i\) tượng trưng cho đường đi ngắn nhất từ \(1\) đến \(i\) trên đồ thị mới.