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ô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): một chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và độ dài của nó là \(c\). Mỗi chuyến bay là một chuyến bay một chiều.
• Bạn có thể giả định rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Output

• In \(n\) số nguyên: độ dài tuyến đường 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\)

Example

Sample input

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

Sample output

0 5 2