prithivMLmods/Coder-Stat

1 2<H1>Problem D: The House of Huge Family</H1>3<p>4Mr. Dango's family has an extremely huge number of members.5Once it had about 100 members, and now it has as many as population of a city.6It is jokingly guessed that the member might fill this planet in the near future.7</p>8 9<p>10Mr. Dango's family, the huge family, is getting their new house.11Scale of the house is as large as that of town.12</p>13 14<p>15They all had warm and gracious personality and were close each other.16However, in this year the two members of them became to hate each other.17Since the two members had enormous influence in the family, they were split into two groups.18</p>19 20<p>21They hope that the two groups don't meet each other in the new house.22Though they are in the same building, they can avoid to meet each other by adjusting passageways.23</p>24 25<p>26Now, you have a figure of room layout. Your task is written below.27</p>28 29<p>30You have to decide the two groups each room should belong to.31Besides you must make it impossible that they move from any rooms belonging to one group to any rooms belonging to the other group.32All of the rooms need to belong to exactly one group.33And any group has at least one room.34</p>35 36<p>37To do the task, you can cancel building passageway.38Because the house is under construction, to cancel causes some cost.39You'll be given the number of rooms and information of passageway.40You have to do the task by the lowest cost.41</p>42<p>43Please answer the lowest cost.44</p>45<p>46By characteristics of Mr. Dango's family, they move very slowly.47So all passageways are escalators.48Because of it, the passageways are one-way.49</p>50 51<h2>Input</h2>52<p>53The input consists of multiple datasets.54Each dataset is given in the following format.55</p>56<pre>57<i>n</i> <i>m</i>58<i>X<sub>1</sub> Y<sub>1</sub> C<sub>1</sub></i>59...60<i>X<sub>m</sub> Y<sub>m</sub> C<sub>m</sub></i>61</pre>62<p>63All numbers in each datasets are integers.64The integers in each line are separated by a space.65</p>66 67<p>68The first line of each datasets contains two integers.69<i>n</i> is the number of rooms in the house, m is the number of passageways in the house.70Each room is indexed from 0 to <i>n</i>-1.71</p>72 73<p>74Each of following <i> m </i> lines gives the details of the passageways in the house.75Each line contains three integers.76The first integer <i>X<sub>i</sub></i> is an index of the room, the starting point of the passageway.77The second integer <i>Y<sub>i</sub></i> is an index of the room, the end point of the passageway.78The third integer <i>C<sub>i</sub></i> is the cost to cancel construction of the passageway.79The passageways, they are escalators, are one-way.80The last dataset is followed by a line containing two zeros (separated by a space).81</p>82 83<H2>Constraints</h2>84<ul>85<li>2 &le; <i> n </i> &le; 100</li>86<li>-10,000 &le; <i>C<sub>i</sub></i> &le; 10,000</li>87<li><i>Y<sub>1</sub></i> ... <i>Y<sub>m</sub></i> can't be duplicated integer by each other.</li>88</ul>89 90<h2>Output</h2>91<p>92For each dataset, print the lowest cost in a line. You may assume that the all of integers of both the answers and the input can be represented by 32 bits signed integers.93</p>94 95<h2>Sample input</h2>96<pre>973 2980 1 2991 2 11002 11010 1 1001022 11030 1 01042 11050 1 -11060 0107</pre>108 109<h2>Sample output</h2>110<pre>11111121001130114-1115</pre>116 117