grup

Ion is the manager of a successful company. Due to the dynamics of the company, each employee must have a cell phone, with which to communicate with the other company employees. Ion pays the phone bill for all the employees and he's trying to cut expenses.
He's recently discovered the "group" voice service which could substantially reduce costs under specific circumstances. More specifically, Ion can select a group of k employees and by activating the group service for those k selected employees, they will pay 50% less for calls to other group members, all other calls being charged at the regular tariff. If an employee from the group calls another member of the group, he will pay 10 RON pennies/minute. For any other call, the regular tariff is of 20 RON pennies/minute. Calls are charged by the minute.
Ion is now analyzing last month's call list for his employees and is trying to establish the group so that the total cost of phone invoices be as small as possible.

Task

Write a program that determines a group of k employees so that, by using the group service, the total cost of phone calls is minimal.

Input Data

Input file grup.in contains on the first line a positive integer k representing the number of employees that should form the group. The second line contains a positive integer N representing the total number of calls from the company employees' call list. Each of the following N lines contains information regarding the calls between company employees, one call per line. The following are specified for a call:
nume1 nume2 d
with meaning "employee nume1 called employee nume2, the call lasted d minutes".

Output Data

Output file grup.out will contain on the first line the minimal total cost of phone calls expressed in RON pennies. The following k lines contain the names of the employees that make up the group, one name per line.

Constraints and Mentions

• 1 <= k <= the number of employees in the company <= 20
• 1 <= N <= 1000
• 1 <= d <= 100
• The names of the employees are maximum 20 characters long (uppercase English alphabet letters).
• If there is more than one solution, display any one of them.
• The order in which the names of the employees in the group are displayed is irrelevant.
• 40% of the score will be granted for determining minimum cost. 100% of the score will be granted for minimum cost and correctly and completely displaying the group of k persons that provide minimum cost.
  

Examples

Time limit: 0.15 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com