Đường Đi Ngắn Nhất I

Có $n$ thành phố và $m$ tuyến bay một chiều. Tìm độ dài đường đi ngắn nhất từ thành phố $1$ đến tất cả các thành phố còn lại.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$, $b$, $c$ — tuyến bay từ $a$ đến $b$ với độ dài $c$.

Dữ liệu ra

In $n$ số nguyên — khoảng cách ngắn nhất từ thành phố $1$ đến từng thành phố $1,2,\dots ,n$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$
• $1\le c\le {10}^9$

Ví dụ