Vấn đề yêu cầu tìm trong số các đường đi ngắn nhất của một đồ thị cho trước, đường đi ngắn nhất có thứ tự từ điển nhỏ nhất

Đầu vào

• Dòng đầu tiên chứa hai số nguyên dương \(n \leq 10^5\) và \(m \leq 10^5\) lần lượt là số đỉnh và số cạnh;
• Mỗi dòng trong \(m\) dòng tiếp theo chứa ba số nguyên dương \(u, v\) và c tương ứng với cung \((u, v)\) và trọng số của nó \(c\);
• Dòng cuối cùng chứa hai số nguyên dương \(s\) và \(t\) lần lượt là đỉnh bắt đầu và đỉnh kết thúc của đường đi yêu cầu.

Đầu ra

• Dòng đầu tiên chứa một số nguyên là trọng số của đường đi kết quả.
• Dòng thứ hai chứa các số nguyên là các đỉnh của đường đi kết quả.

Input:

4 6
2 1 3
2 3 1
3 1 10
4 1 5
3 4 5
4 2 6
2 4

Output:

6
2 3 4