MKTHPATH - Kth Shortest Path

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


Added by:psetter
Date:2009-02-23
Time limit:0.600s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 ERL JS-RHINO NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Yokohama 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.