Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem H
The ‘Hire-a-Coder’ Business Model
Input: Standard Input

Output: Standard Output

As some other websites, ‘Hire-a-Coder’ is a new website that works as an agent between custom software buyers & freelance software developers. According to the ‘Hire-a-Coder’ business model, a number of clients are registered in the system. Some of them are software buyers. They post custom software projects on the site. Then the coders bid on the projects & each of the projects is assigned to a single particular coder after the biddings & dealings. Any buyer may have more than one open project at a time. Similarly any coder can take up more than a single project at any time. But no coder is allowed to take multiple projects from the same buyer at a time. The site works as a medium in the total procedure. Now, if a coder successfully completes his assigned project & the buyer accepts his work, ‘Hire-a-Coder’ gets some commission for that. But if the coder fails to complete a project or satisfy the client with his work, the company has to pay a penalty to the buyer thus suffering a loss.

Recently it is found out that there are a number of fake coders that take up a project but never finish their work eventually causing the company a good amount of loss. So, they need someone to advise them which of the possible project assignments are to make & which are to avoid in order to minimize their loss.

Assume, all the registered clients of the company are denoted by a unique positive integer number between 1 & N. By the help of a great fortune-teller, they have already tabulated the future of assigning all possible buyer-coder pairs. You can assume that assigning any project from a particular buyer to a particular coder has the same future. In their tabulation, if a coder fails to do a project from a buyer, a positive integer value is assigned to this particular buyer-coder pair. The value indicates the amount of loss the company is going to suffer if they pair-up these two clients. On the other hand, in case of a successful completion of a project from a buyer-coder pair, a negative integer value is assigned to this pair which denotes negative loss i.e. amount of profit.

You are assured that, every single individual in the community has a communication link to all other people in this community, not necessarily through direct acquaintance. The link may well be via one or more other people. Also note that, if ‘A’ knows ‘B’ then ‘B’ always knows ‘A’.

There’s one more problem. You have the pairing information for all those N people but you don’t know which of them are buyers & which of them are coders. But you know that, all the registered clients are either a buyer or a coder & there’s no one who is a buyer & a coder simultaneously. If the data for any test case violates this assumption, print “Invalid data, Idiot!” & stop processing that case further.

Now, bearing all these factors in mind, you are to select a subset of the possible pairings so that if the company makes strictly those assignments, their loss is minimum possible. Also, you have to choose the subset so that every single person still has a direct / indirect communication link to all other people.

Input

Every test case starts with a single positive integer N (2<=N<=200) which is the number of registered clients. The second line has another positive integer E (1<=N<=11000), the number of pairs tabulated by the fortune-teller. Each of the next E lines contains 3 integers A,B & C which means, if the company pairs A with B, they will end up in a  loss with amount C. (1<=A,B<=N and -1000<=C<=1000). The last test case will be followed immediately by a single line containing a 0. This line indicates the end of file.

Output

If the there is any inconsistency in the data (as described in the statement) print “Invalid data, Idiot!” in a single line. Otherwise, print the minimum possible loss the company can afford without disconnecting the social network.

Problemsetter: Mohammad Mahmudur Rahman

Special Thanks To: Manzurur Rahman Khan