Mùa xuân về trên khắp nẻo đường, đất trời như khoác lên mình tấm áo mới rực rỡ. Tiết trời se lạnh dần tan biến, nhường chỗ cho những tia nắng ấm áp và hương hoa tràn ngập không gian. Trong không khí ấy, có một chàng sinh viên tên Tăng - vốn vừa lãng mạn, vừa có phần ngây thơ - đang ấp ủ một ước mơ nhỏ bé nhưng mãnh liệt: "một chuyến du xuân cùng người con gái mà anh thầm thương trộm nhớ bấy lâu".

Tăng không giàu có. Số tiền tiết kiệm từ việc làm thêm và sinh hoạt tằn tiện suốt năm qua chẳng đáng là bao. Nhưng tình cảm chân thành của anh thì lại rất lớn. Anh muốn dùng tất cả những gì mình có, không phải để tổ chức một chuyến đi xa hoa, mà là để tạo nên một hành trình giản dị nhưng trọn vẹn, một vòng tròn khép kín tượng trưng cho tình yêu không điểm bắt đầu và cũng chẳng có điểm kết thúc.

Thế nhưng, đời vốn dĩ chẳng dễ dàng. Khi tìm đến công ty lữ hành để xin thông tin, Tăng không nhận được danh sách tour sẵn có nào. Thay vào đó, nhân viên chỉ đưa cho anh một tấm bản đồ cũ kỹ, trên đó vẽ nên ~N~ thành phố và một số tuyến đường hai chiều nối chúng lại với nhau. Trên mỗi tuyến đường đều ghi rõ chi phí đi lại.

Anh bối rối nhìn tấm bản đồ, nhưng rồi chợt nghĩ: "Có lẽ, đây chính là thử thách mà số phận đặt ra cho mình. Nếu mình thật sự muốn ở bên cô ấy, mình phải tìm được một chuyến đi đẹp nhất - vừa tiết kiệm, vừa ý nghĩa, vừa đủ dài để có thật nhiều kỷ niệm."

Trong lòng Tăng, những tiêu chí cho chuyến hành trình đã hình thành rõ ràng:

1. Xuất phát từ một thành phố nào đó, và cuối cùng quay trở lại đúng thành phố ấy. Vì chỉ có như vậy, hành trình mới trở thành một vòng tròn hoàn hảo - vòng tròn mà anh ngầm ví như lời hẹn ước: tình yêu bắt đầu nơi đâu thì sẽ trở lại nơi đó, mãi mãi chẳng bao giờ lạc mất.

2. Mỗi thành phố đi qua chỉ được ghé một lần duy nhất, trừ thành phố xuất phát - nơi mà cả hành trình kết thúc, như trái tim Tăng, chỉ muốn một lần duy nhất thuộc về một người.

3. Hành trình phải ghé ít nhất ~K~ thành phố. Vì Tăng không muốn chuyến đi quá ngắn ngủi - tình yêu cần những kỷ niệm, cần những khoảng lặng, cần cả những đoạn đường dài để họ có thể đi bên nhau, chia sẻ và thấu hiểu.

4. Tổng chi phí phải là ít nhất có thể. Bởi chỉ khi tiết kiệm, Tăng mới có thể dành phần còn lại để mua một bó hoa tươi - gửi đến cô gái như lời tỏ tình chân thành nhất sau khi chuyến đi kết thúc.

Nếu tìm được hành trình như vậy, Tăng sẽ có thể trao cho cô ấy một mùa xuân trọn vẹn, một ký ức mà cả đời chẳng thể quên. Nếu không, anh chỉ biết ngồi bên cửa sổ, nhìn hoa đào rơi và tự nhủ: "Có lẽ mình phải đợi một mùa xuân khác..."

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N, M, K~:
  • ~N~: số lượng thành phố. ~(N \leq 5000)~
  • ~M~: số lượng tuyến đường hai chiều trực tiếp nối giữa các thành phố. ~(M \leq 1000)~
  • ~K~: số lượng thành phố tối thiểu mà chuyến đi phải đi qua. ~(2 < K < N)~
• Tiếp theo là ~M~ dòng, mỗi dòng gồm ba số nguyên dương ~u, v, w~:
  • ~u, v~: hai thành phố được nối trực tiếp ~(1 \leq u, v \leq N)~.
  • ~w~: chi phí đi lại của tuyến đường đó ~(1 \leq w \leq 10^6)~.

Output

• Nếu tìm được chuyến đi thỏa mãn:
  • In ra hai dòng:
    • Dòng ~1~: số ~C~, là chi phí nhỏ nhất của chuyến đi.
    • Dòng ~2~: số lượng thành phố có trong chuyến đi.
• Nếu không tìm được, in ra: -1

Sample Input 1

5 6 3
1 4 1 
1 2 16
1 3 300
2 3 50
2 5 15
3 5 20

Sample Output 1

85
3

Sample Input 2

4 3 4
1 2 10
1 3 20
1 4 30

Sample Output 2

-1

Ràng buộc

• ~30\%~ số test có ~N \leq 25~.
• ~25\%~ số test có ~N \leq 50~.
• ~20\%~ số test có ~N \leq 100~.
• ~15\%~ số test có ~N \leq 1000~.
• ~10\%~ số test có ~N \leq 5000~.