Cho một đồ thị có hướng, có trọng số với thành phố và chuyến bay (từ thành phố có thể đi đến tất cả các thành phố khác thông qua các chuyến bay một chiều này).
Nhiệm vụ của bạn là tìm độ dài của tuyến đường ngắn nhất từ thành phố đến mỗi thành phố khác.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và là số thành phố và số chuyến bay.
dòng tiếp theo mô tả các chuyến bay. Mỗi dòng chứa ba số nguyên cho biết có một chuyến bay từ thành phố đến thành phố với chi phí là .
Kết quả: In ra số nguyên lần lượt là độ dài của các tuyến đường ngắn nhất từ thành phố 1 đến các thành phố .
