Bảng khoảng cách từ trung tâm

Bối cảnh và bài toán

Trung tâm điều phối số 1 cần biết chi phí tối thiểu để gửi dữ liệu đến mọi nút còn lại trong mạng có hướng với chi phí không âm.

Yêu cầu

Tính khoảng cách ngắn nhất từ nút 1 tới tất cả n nút. Nếu nút không thể tới, in -1 tại vị trí đó.

Input

Dòng đầu n, m; tiếp theo m cạnh có hướng u, v, w.

Output

In n số là khoảng cách từ 1 tới các nút 1..n, dùng -1 nếu không tới được.

Ràng buộc

• 1 <= n <= 10^5
• 0 <= m <= 2*10^5
• 0 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–04 | | S2 | 60 | Không có ràng buộc bổ sung | 05–10 |

Ví dụ 1

Input

4 5
1 2 5
1 3 2
3 2 1
2 4 2
3 4 7

Output

0 3 2 5

Giải thích. Dijkstra từ nút 1 tạo bảng khoảng cách ngắn nhất tới mọi nút.

Ví dụ 2

Input

3 1
1 2 4

Output

0 4 -1

Giải thích. Dijkstra từ nút 1 tạo bảng khoảng cách ngắn nhất tới mọi nút.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Shortest Routes I. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.