Tìm đường đi ngắn thứ k của đồ thị.

Input

NHiều test, mỗi test có dạng: 

    n	m	k	a	b
    x1	y1	d1	
    x2	y2	d2

    …
    xm	ym	dm

n là số đỉnh, 2 ≤ n ≤ 50. 
m là số cạnh(có hướng), a là đỉnh nguồn, b đích,
biết 1 ≤ k ≤ 200 và a ≠ b.

Cạnh thứ i nối 2 đỉnh xi và yi có độ dài di (1 ≤ i ≤ m). 
,1<= xi,yi <= n,
1<= di <=10000,  
Có cả trường hợp m = 0 và m = n(n − 1).

Kết thúc là bộ 5 số 0.

SAMPLE INPUT
5 20 10 1 5
1 2 1
1 3 2
1 4 1
1 5 3
2 1 1
2 3 1
2 4 2
2 5 2
3 1 1
3 2 2
3 4 1
3 5 1
4 1 1
4 2 1
4 3 1
4 5 2
5 1 1
5 2 1
5 3 1
5 4 1
4 6 1 1 4
2 4 2
1 3 2
1 2 1
1 4 3
2 3 1
3 4 1
3 3 5 1 3
1 2 1
2 3 1
1 3 1
0 0 0 0 0

Output

 
Nếu có < k đường đi từ a đến b, in ra "None". 
Ngược lại in ra đường ngắn thứ k theo thứ tự các đỉnh từ a->b, cách nhau bằng dấu trừ, -.
 
ĐƯờng đi P và Q được so sánh theo cách:
   1. Độ dài của P < độ dài của Q.
   2. Hai độ dài bằng nhau, P đứng trước Q theo thứ tự từ điển. 

SAMPLE OUTPUT
1-2-4-3-5
1-2-3-4
None