Mô tả

Cho đồ thị có hướng $n$ đỉnh $m$ cạnh có trọng số không âm. Tìm đường đi ngắn nhất từ đỉnh $1$ đến tất cả các đỉnh.

Input

• Dòng 1: $n,\ m$ ($2 \le n \le 10^5$, $0 \le m \le 5 \cdot 10^5$)
• Tiếp theo $m$ dòng: $u\ v\ w$

Output

$n$ số là khoảng cách ngắn nhất ($-1$ nếu không tới được).