Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KWAY - Trao đổi thông tin

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 chung bất kỳ một đường 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 là n, m, k, s, f (n ≤ 100).
- m dòng tiếp là u, v, c cho biết có đường từ u -> v và v -> u với chi phí là c.

Output

- Dòng đầu ghi –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 để 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)

Chú ý: Phạm vi tính toán là Longint.

Example

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

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


Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-09-14
Thời gian chạy:0.301s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2015-08-14 05:27:29
giới hạn k sao nhỏ thế
2015-06-26 05:09:48 Thất Dạ Chí Quỷ
quen ko ghi -1 ma van full
2014-09-05 17:14:02 Thcs Ðặng Chánh Kỷ
xuất phát từ bài mincost để code bài này, ac phát đầu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.