Time Limit: 1s
Memory Limit: 256MB
Bài toán yêu cầu trong số các đường đi ngắn nhất trên một đồ thị hãy tìm và đưa ra đường đi có thứ tự từ điển nhỏ nhất.
Dòng đầu chứa hai số nguyên dương n ≤ 105, m ≤ 105 là số đỉnh và số cạnh của đồ thị;
m dòng sau mỗi dòng chứa ba số nguyên dương u, v và c tương ứng là một cung (u,v) và trọng số c trên cung đó;
Dòng cuối cùng chứa hai số nguyên dương s và t và đỉnh đầu và cuối của đường đi cần tìm.
Dòng đầu tiên chứa 1 số nguyên là độ dài của đường đi tìm được.
Dòng thứ 2 chứa các số nguyên là các đỉnh của đường đi tìm được.
4 6 2 1 3 2 3 1 3 1 10 4 1 5 3 4 5 4 2 6 2 4
6 2 3 4