Cho đồ thị vô hướng có trọng số có đỉnh, cạnh, cạnh có trọng số và hai đỉnh . Hãy tìm đường đi ngắn nhất từ đến .
Dữ liệu vào:
- Dòng đầu chứa bốn số nguyên là số đỉnh và số cạnh của , đỉnh xuất phát và đỉnh đích;
- dòng tiếp theo, mỗi dòng chứa ba số số cho biết một cạnh nối hai đỉnh và trong và trọng số tương ứng.
Dữ liệu ra:
- Dòng đâu ghi số nguyên là độ dài đường đi ngắn nhất;
- Dòng thứ hai ghi ra một đường đi từ tới có độ dài ngắn nhất.
Ví dụ:
Dữ liệu vào:
3 3 1 3
1 2 3
2 3 1
1 3 5
Dữ liệu ra:
Giới hạn:
- .
