Đường đi ngắn nhất I

Trong một vụ án phức tạp, FullHouse Dev được một luật sư thuê để giải quyết một bài toán về tìm đường đi ngắn nhất giữa các thành phố.

Bài toán

Có \(n\) thành phố và \(m\) đường bay kết nối giữa chúng. Nhiệm vụ của FullHouse Dev là xác định độ dài đường đi ngắn nhất từ thành phố Syrjälä đến mọi thành phố khác. Các thành phố được đánh số từ \(1\) đến \(n\), trong đó Syrjälä là thành phố số \(1\).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và số đường bay.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): đường bay bắt đầu từ thành phố \(a\), kết thúc tại thành phố \(b\), và có độ dài \(c\). Mỗi đường bay là một chiều.
• Có thể đảm bảo rằng luôn có thể đi từ Syrjälä đến tất cả các thành phố khác.

OUTPUT FORMAT:

• In ra \(n\) số nguyên: độ dài đường đi ngắn nhất từ Syrjälä đến các thành phố \(1,2,\dots,n\).

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Ví dụ

INPUT

3 4
1 2 6
1 3 2
3 2 3
1 3 4

OUTPUT

0 5 2

Giải thích

• Độ dài đường đi ngắn nhất từ thành phố 1 (Syrjälä) đến chính nó là 0
• Độ dài đường đi ngắn nhất đến thành phố 2 là 5 (đi từ 1 → 3 → 2)
• Độ dài đường đi ngắn nhất đến thành phố 3 là 2 (đi trực tiếp từ 1 → 3)