Cho một đồ thị vô hướng có trọng số G=(V,E), gồm n đỉnh và m cạnh.
Mỗi cạnh nối hai đỉnh u, v có trọng số w≥0.

Cho trước một đỉnh nguồn s (xuất phát).

Yêu cầu: Tìm độ dài đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại trong đồ thị.

Dữ liệu vào: test.inp

• Dòng 1: ba số nguyên n, m, s
• m dòng tiếp theo, mỗi dòng gồm ba số nguyên u, v, w là cạnh (u, v) và trọng số w của cạnh đó

Dữ liệu ra: test.out

• Ghi ra n dòng
• Dòng thứ i ghi khoảng cách ngắn nhất từ s đến đỉnh i và thứ tự các đỉnh để đi từ s đến i dạng: <khoảng cách> | s, …

Nếu không tồn tại đường đi từ s đến i thì ghi: KHONG