Dijkstra Intro

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 tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và số 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.

Ràng buộc: \(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\).

Output

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

Sample Input 1

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

Sample Output 1

0 5 2