Cạnh trọng số âm

Cho đồ thị có hướng gồm $n$ đỉnh đánh số từ $1$ đến $n$ và $m$ cung. Cung thứ $i$ đi từ đỉnh $u_i$ tới đỉnh $v_i$ với trọng số $w_i$; trọng số có thể âm. Có thể có cung từ một đỉnh tới chính nó và nhiều cung giữa cùng một cặp đỉnh.

Đồ thị được đảm bảo không có chu trình âm: mọi chu trình (đi theo chiều các cung) đều có tổng trọng số không âm.

Với mỗi đỉnh $v$, hãy tính độ dài đường đi ngắn nhất từ đỉnh $1$ tới $v$ (tổng trọng số các cung trên đường đi).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.

Dữ liệu ra

In ra trên một dòng $n$ giá trị cách nhau bởi dấu cách: giá trị thứ $v$ là độ dài đường đi ngắn nhất từ $1$ tới $v$, hoặc INF nếu không có đường đi từ $1$ tới $v$.

Ràng buộc

• $1\le n\le 1000$
• $0\le m\le 3000$
• $1\le u_i,v_i\le n$
• $-{10}^9\le w_i\le {10}^9$
• Đồ thị không có chu trình âm.

Ví dụ