Barátok

Barátok között előfordul, hogy kölcsönadnak egymásnak kisebb-nagyobb pénzösszegeket. Ösztöndíj fizetésekor azonban kiegyenlítik a tartozásokat. Ezért pontosan feljegyzik, hogy ki kitől, mekkora összeget vett kölcsön. Szeretnék optimalizálni a tartozások kiegyenlítését, azaz a legkevesebb pénzmozgatással megoldani.

Feladat

Írj programot, amely

• kiszámítja azt a legkisebb pénzösszeget, amely a tartozások optimális kiegyenlítése során átutalásra kerül
• megad egy, kiegyenlítést eredményező, optimális átutalási sorozatot.

Bemenet

A BARATOK.BE szöveges állomány első sora a barátok N (0 < N <= 10000) számát tartalmazza. A barátokat a sorszámukkal azonosítjuk 1-től N-ig. A második sorban a tranzakciók K száma áll (0 <= K <= 30000). A következő K sor mindegyike három egész számot; X, Y , P, (0 <= X, Y <= N, N != Y , 0 < P <= 30000) tartalmaz egy-egy szóközzel elválasztva, ami egy tranzakciót ír le, az X személy az Y személytől P összeget vett kölcsön a hónap során valamikor.

Kimenet

A BARATOK.KI szöveges állomány első sorába azt a minimális összeget kell írni, amennyi a tartozások optimális kiegyenlítése esetén átutalásra kerül. A következő sorokban kell megadni egy kiegyenlítést eredményező optimális átutalási sorozatot. Minden sorban három szám szerepeljen egy-egy szóközzel elválasztva, X Y P, ami azt jelenti, hogy az X személy az Y személynek P összeget utal át a kiegyenlítés során. Nem kikötés, hogy X kölcsönkért Y-tól, és előfordulhat, hogy egy személy több másik személynek is átutal a megoldásban.

Példa

(Olimpiai válogatóverseny 2000)