THỰC HÀNH

Trong một mạng gồm N máy tính đánh số từ 1 đến N. Sơ đồ nối mạng được cho bởi m kênh nối trực tiếp giữa một số cặp máy trong mạng. Biết chi phí truyền một đơn vị thông tin theo mỗi kênh nối của mạng.

Người ta cần chuyển một bức thông điệp từ máy S đến máy D (S ≠ D). Để đảm bảo an toàn, người ta muốn chuyển bức thông điệp này theo hai đường truyền tin khác nhau (tức là không có kênh nào của mạng được sử dụng trong cả hai đường truyền tin). Chi phí của một đường truyền tin được hiểu là tổng chi phí trên các kênh của nó. Chi phí truyền thông điệp bằng tổng chi phí của hai đường truyền.

Yêu cầu: Giả sử bức thông điệp có độ dài là 1 đơn vị thông tin, hãy tìm cách truyền thông điệp từ S đến D sao cho chi phí truyền thông điệp là nhỏ nhất

Dữ liệu vào:

• Dòng đầu tiên ghi bốn số n, m, S, D (2 ≤ n ≤ 100);
• Mỗi dòng thứ i trong số m dòng tiếp theo ghi thông tin về kênh nối thứ i của mạng gồm ba số a_i, b_i, c_i, trong đó a_i, b_i là chỉ số của hai máy tương ứng với kênh này và c_i (nguyên dương ≤ 200) là chi phí để truyền một đơn vị thông tin từ máy ai đến máy b_i (và ngược lại) theo kênh này (i=1,2,...,m).

Dữ liệu ra:

• Dòng đầu tiên ghi chi phí truyền thông điệp theo cách truyền tin tìm được.
• Dòng thứ hai ghi đường truyền tin thứ nhất dưới dạng dãy có thứ tự các máy, bắt đầu từ máy S và kết thúc ở máy D.
• Dòng thứ ba ghi đường truyền tin thứ hai dưới dạng dãy có thứ tự các máy bắt đầu từ máy S và kết thúc ở máy D.
• Nếu không tồn tại cách truyền thì chỉ cần ghi một dòng: “NO SOLUTION”
• Các số trên một dòng của Input/ Output file ghi cách nhau ít nhất một dấu cách.

Ví dụ:

Dữ liệu vào:
5 7 1 5
1 2 3
1 4 8
2 3 5
2 4 4
3 5 5
4 3 8
4 5 3
Dữ liệu ra:
24
1 2 3 5
1 4 5