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 tuyến đường ngắn nhất từ Syrjälä đến mọi thành phố.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots,n\) và thành phố \(1\) là Syrjälä.
• Sau đó có \(m\) dòng, mỗi dòng mô tả một chuyến bay một chiều bằng ba số nguyên \(a, b, c\): bay từ thành phố \(a\) đến \(b\) với độ dài \(c\).
• Bảo đảm có thể đi từ Syrjälä (thành phố \(1\)) tới mọi thành phố khác.

Output

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

Constraints

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

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

0 5 2