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.|

VMCOMP - Công việc tuyển dụng

Năm 2020, Raldono trở thành giám đốc nhân sự tại công ty IONV. Trong đợt tuyển nhân viên mới lần này, có N ứng viên, được đánh số từ 1 đến N, nộp hồ sơ đăng kí. Là một công ty hàng đầu với nhiều dự án lớn cần thực hiện, IONV luôn muốn các nhân viên của mình có kĩ năng làm việc nhóm hiệu quả nhất. Do đó, bên cạnh những yếu tố thông thường mà các nhà tuyển dụng hay quan tâm, Raldono sẽ ưu tiên cho những ứng viên đã từng có kinh nghiệm làm việc chung với các ứng viên khác. Theo tiêu chí này, Raldono đã tổng hợp được một danh sách M cặp ứng viên (u, v) đã từng làm việc với nhau và biết được độ hiệu quả của họ, kí hiệu là E(u, v).

  • Độ hiệu quả của một ứng viên u được tính bằng tổng E(u, v) với điều kiện cả 2 ứng viên u và v cùng được tuyển.
  • Độ hiệu quả của công ty sau đợt tuyển nhân viên mới sẽ tăng một giá trị bằng với độ hiệu quả nhỏ nhất của một ứng viên được chọn.

Ban lãnh đạo công ty yêu cầu độ hiệu quả của công ty phải tăng không ít hơn S. Hãy giúp Raldono tìm số lượng ứng viên lớn nhất có thể được tuyển và in ra danh sách các ứng viên đó. Nếu có nhiều danh sách thỏa, in ra một danh sách bất kì. Nếu không có cách tuyển thỏa yêu cầu, in ra -1.

Input

  • Dòng 1 chứa 3 số nguyên N, M S.
  • M dòng tiếp theo mỗi dòng chứa 3 số nguyên u, v E(u, v). Mỗi cặp số (u, v) chỉ xuất hiện tối đa 1 lần.

Output

  • Dòng 1 in ra số K tương ứng với số lượng ứng viên lớn nhất có thể được tuyển hoặc -1.
  • Nếu có cách tuyển thỏa yêu cầu, dòng 2 in ra K số tương ứng với các ứng viên được tuyển theo thứ tự tăng dần.

Giới hạn

  • 1 ≤ N, M, E(u, v) ≤ 100000
  • 1 ≤ u, v ≤ N
  • 1 ≤ S ≤ 109
  • Trong 20% số test, N ≤ 20
  • Trong 50% số test, N ≤ 1000

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 2 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:

4 4 15
1 2 10
2 3 20
2 4 5
3 4 8

Output:

2
2 3


Input:

3 2 7
1 2 3
1 3 1

Output:

-1 

Được gửi lên bởi:VOJ Team
Ngày:2013-06-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:VM13 - Nguyễn Tấn Sỹ Nguyên

hide comments
2019-10-08 04:12:39
1 đấm AC :))))
2017-11-30 08:30:51
nhật hào sạch
2017-11-11 16:23:07
Hell elo 34đ :(
2017-04-04 03:12:04
ryzeeeee vô đối.
cm tuổi lz
2016-10-24 17:19:21
50 điểm : Xài heap
90 điểm : để long long
Thank me later :))
2013-07-06 08:25:16 a;slkfjasl;fkj
tốt thật, bài ni hay đó :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.