Mô tả bài toán: Đường đi ngắn nhất

Có n thành phố và m chuyến bay giữa chúng. Nhiệm vụ của bạn là xác định độ dài của đường đi ngắn nhất từ thành phố Syrjälä (thành phố 1) đến tất cả các thành phố khác.

Input:

• Dòng đầu tiên chứa hai số nguyên n và m: số lượng thành phố và số lượng chuyến bay.
• Tiếp theo, có m dòng, mỗi dòng chứa ba số nguyên a, b, và c:
  • ~a~: thành phố xuất phát.
  • ~b~: thành phố đích.
  • ~c~: độ dài chuyến bay từ ~a~ đến ~b~.
• Mỗi chuyến bay là chuyến bay một chiều.

Bạn có thể giả định rằng luôn có thể đi từ thành phố Syrjälä đến tất cả các thành phố khác.

Output:

• In ra n số nguyên: độ dài đường đi ngắn nhất từ Syrjälä (thành phố 1) đến các thành phố từ 1 đến ~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
2 3 3
1 3 4

Output:

0 5 2

Giải thích:

• Có 3 thành phố và 4 chuyến bay.
• Độ dài đường đi ngắn nhất từ thành phố 1 đến các thành phố:
  • Đến thành phố 1: ~0~ (bắt đầu tại đây).
  • Đến thành phố 2: ~5~ (qua đường 1 → 3 → 2).
  • Đến thành phố 3: ~2~ (qua đường 1 → 3).