Z a d a n i e 1 Dany jest graf nieskierowany.
Kazda krawedz ma pewna wage. Jesli waga jest wieksza od zera, to sie nie zmienia. Jesli waga jest mniejsza lub rowna 0, wtedy po przejsciu przez te krawedz ma wartosc o 1 wieksza.
(np. na poczatku - z pliku wejsciowego -3, potem -2, potem -1, potem 0, potem 1 i dalej bez zmian) Nalezy znalezc w grafie takie przejscie od wierzcholka nr 1 do wierzcholka koncowego (numer=liczba wierzcholkow,) aby uzyskac najmniejsza mozliwa sume z przejscia krawedziami.
(mozna byc wiele razy w wierzcholkach, takze w pierwszym i ostatnim)


Wejscie:

Liczba wierzcholkow
Liczba krawedzi
Kolejne krawedzie: skad, dokad, waga


Wyjscie:

Zysk
Ciag wierzcholkow


Przyklad:


Wejscie:

3
3
1 2 -3
2 3 3
1 3 1

Wyjscie:

-5
1 2 1 2 1 3

Zadanie nalezy oddac najpozniej na laboratorium 4 kwietnia godz. 13:45.
Nalezy rowniez przeslac na adres franekg(at)mimuw.edu.pl