Cho đồ thị có hướng có trọng số gồm n đỉnh và m cung.

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

INPUT

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

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c cho biết có cung u-v với trọng số c. (1 ≤ u, v ≤ n; |c| ≤ ${10}^4$).

Lưu ý trọng số có thể âm.

OUTPUT

Ghi ra các đỉnh trên đường đi ngắn nhất từ s đến t. Nếu không có đường đi thì ghi ra số -1.

Ví dụ:

Input

5 7 2 3
1 3 8
1 5 -7
4 1 12
2 5 8
2 4 5
3 5 1
5 4 -4

Output:

2 5 4 1 3

Bài dễ hơn