Problem
Bạn được cung cấp một biểu đồ trọng số có hướng. Bạn cần tìm khoảng cách từ 1 trên cùng đến tất cả các cái khác, sử dụng thuật toán 1 - k BFS.
Đầu vào
Dòng đầu tiên chứa 2 số nguyên n và m, tương ứng là số đỉnh và số cạnh trong đồ thị. Các dòng m sau đây chứa 3 số mỗi dòng a và b - các đỉnh mà cạnh kết nối và c - các đỉnh trọng số của cạnh này (a, b, c >= 0).
Đầu ra
Cần xuất ra số n-1 được phân tách bằng dấu cách - khoảng cách từ 1 trên cùng đến tất cả các số khác, nếu không có đường dẫn khả dĩ nào từ 1 đến đỉnh i, sau đó bạn cần xuất Impossible.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
|
1 4 3 6 4 Không thể Không thể Không thể
|