75. Hidak

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 szerkezete: elsőként a megoldandó feladatok száma van megadva, majd feladatonként adottak a következők: a partokon lévő pontok száma (n), a lehetséges hidak száma (h), majd h egymást követő 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)

 

input (t0.txt): output:
5
3
4
1 1 3
1 2 4
2 2 3
2 3 1
2
4
1 1 1
1 2 2
2 1 4
2 2 3
2
4
1 1 1
1 2 3
2 1 2
2 2 4
2
4
1 1 1
1 2 3
2 1 4
2 2 2
2
4
1 1 1
1 2 6
2 1 2
2 2 3
 1. feladat: 6

2. feladat: 4

3. feladat: 5

4. feladat: 4

5. feladat: 6


(ACM feladat nyomán)

Tesztfájlok: