Cho một mạng thông tin gồm ~n~ trạm và ~m~ đường nối hai chiều giữa các trạm. Trạm ~s~ là trạm chỉ huy, trạm ~f~ là trạm điều khiển. Sau một lần bị tin tặc tấn công lấy mất dữ liệu từ trạm chỉ huy chuyển đến trạm điều khiển, chỉ huy mạng quyết định chia thông tin chuyển đi thành ~k~ đơn vị thông tin để chuyển theo ~k~ đường đến trạm điều khiển. Mà hai đường truyền bất kỳ không được dùng chung một đường nối nào.

Hãy tìm cách truyền ~k~ đơn vị thông tin sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa năm số nguyên ~n~, ~m~, ~k~, ~s~, ~f~ ~(1 \leq n \leq 100, 1 \leq m \leq 5000, 1 \leq k \leq 100, 1 \leq s, f \leq n)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~u~, ~v~ và ~c~ ~(1 \leq u, v \leq n, 1 \leq c \leq 10^9)~, cho biết có một đường đi hai chiều nối giữa ~u~ và ~v~ với chi phí truyền tin là ~c~.

Output

• Dòng đầu tiên in ra số ~-1~ nếu không thể chuyển ~k~ đơn vị thông tin theo cách trên, ngược lại ghi chi phi nhỏ nhất để chuyển.
• ~k~ dòng tiếp lần lượt ghi cách chuyển của từng đơn vị thông tin. Số đầu là số lượng trạm trên đường truyền, tiếp đó là dãy các trạm trên đường truyền (bắt đầu từ ~s~, kết thúc ở ~f~).

Sample Input

8 11 3 1 8
1 2 1
1 4 1
1 5 1
2 3 1
2 4 1
2 7 1
3 8 1
3 6 1
3 5 1
6 8 1
7 8 1

Sample Output

11
4 1 2 3 8
5 1 4 2 7 8
5 1 5 3 6 8