Cho n địa điểm, giữa 2 địa điểm có thể có đường đi trực tiếp. Có tất cả m đường đi trực tiếp.

Tìm đường đi nhỏ nhất từ địa điểm s đến địa điểm t.

INPUT

Dòng đầu là 4 số nguyên dương: n, m, s, t (n ≤ ~10^5~; m ≤ ~2.10^5~; 1 ≤ s, t ≤ n)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương u, v, c cho biết có đường đi nối 2 địa điểm u và v với độ dài c. (1 ≤ u, v ≤ n; c ≤ ~10^4~).

OUTPUT

Dòng 1 ghi ra độ dài đường đi, nếu không có đường đi ghi ra -1;

Dòng 2 ghi ra các địa điểm trên đường đi ngắn nhất từ s đến t.

Ví dụ:

Input

5 7 2 1
1 3 8
1 5 7
1 4 12
2 5 11
2 4 5
3 5 16
5 4 4

Output:

16
2 4 5 1