PEG Judge - WC02 - S

Woburn Challenge 2002 - Suicidal

Problem 3: Evil Tasks

As Frodo woke up from his near eternal nightmare, having been stabbed by the enchanted sword of the Lost Kings, he began to consider the events carefully. How did the orcs and the Black Riders always stay just one step behind them? What secret power did they possess? Just then, Bilbo Baggins entered the elf chamber. ”There you are my dear Baggins" - he noticed Frodo deep in thought - "What is troubling you?"

"I am wondering how the evil forces can remain so efficient...."

"'Tis not a real secret" answered Bilbo. "Before his defeat at Mordor, Sauron had invented a machine he called a computer. Apparently, it is a kind of counting device, very efficient at creating a sort of bug. Next, if you possess the dark and secret knowledge of lacsap it is apparently possible for the machine to hand out tasks for all the members of Sauron's forces. Well, at least that's how the story goes. I don't know, I really don't know."

Bilbo shook his head "What did I get you into. I'm sorry dear Frodo, I'm sorry...." He left the room, sad and solemn.

Frodo started wondering, "A dynamic, parallel task scheduling program... if only I had brought my Z/Z-- book...". Before he could complete his train of thought it was interrupted by the late arrival of a familiar and most welcome figure: Gandalf.

Given a number N ≤ 101 of evil guys and a number M ≤ 101 of evil tasks, where each task takes a multiple of 1 standard hour, find the shortest time to execute all of the tasks. The evil guys - orcs, especially - are not so clever so you will also need to print out a schedule for them, as to when to execute the task. Also, the orcs are not very coordinated so only one orc can work on one task during any given time interval.

Note that the evil guys/tasks which appear in the input will be in the range [1..N] / [1..M] (respectively), although not all the numbers in a range have to be used.

Input

Each case begins with two integers, N and M.
The following lines will specify the possible combinations of orc-task assignments with 3 integers: orc #, task #, and time units required for said orc to finish said task (-1 -1 -1 denotes end of orcs / tasks)

The last test case will have N, M = -1.

Output

Time required (standard hours)
For each 1 hour time period, print out the orcs which will be completing their tasks – as well as the corresponding task in parentheses – during that period, as shown below.