Ceeville városát az Ansi folyó szeli ketté. A város vezetése szeretne állandó hidakat építeni, hogy így biztosítsa az összeköttetést a két városrész közt.

A hidak tervezéséhez a város műszaki elitjét hívta segítségül. A statikusok megállapították, hogy a folyó két partján mely n-n pontról lehet hidat indítani, és mely hidakat lehet megépíteni, a várostervezők megbecsülték, hogy egy híd megépítése mekkora haszonnal jár. Végül a C++ programozókat hívták, hogy mondják meg, mely hidakat építsék meg. A programozóknak figyelembe kell venniük, hogy két híd nem keresztezheti egymást, és a part egy pontjához csak egy hidat lehet építeni.

A bemeneti file-ban adott n, a partokon lévő pontok száma, h a lehetséges hidak száma, majd h sor, minden sorban 3 szám: az egyik part melyik pontjáról, a másik part melyik pontjára, mekkora haszonnal lehet hidat építeni.
 

A kimeneti file tartalmazza, hogy mekkora összhaszon érhető el.

Példa:


(a négy híd közül az 1-1 és 2-2, 3 és 3 értékűeket kell megépíteni)

 

(ACM feladat nyomán)

input0.txt
input1.txt
input2.txt
input3.txt
input4.txt
input5.txt
input6.txt
input7.txt
input8.txt