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 ktoregos wierzcholka, aby uzyskac najmniejsza mozliwa sume z przejscia krawedziami (docelowy wierzcholek jest dowolny)
(mozna byc wiele razy w wierzcholkach, takze w pierwszym i ostatnim odwiedzanym).
Znaleziony wynik niekoniecznie musi byc optymalny, ale im lepszy, tym lepiej.

Wejscie:

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


Wyjscie:

Zysk
Liczba wierzcholkow w rozwiazaniu
Ciag wierzcholkow


Przyklad:


Wejscie:

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

Wyjscie:

-6
5
1 2 1 2 1


Ograniczenia:
Liczba wierzcholkow 100
Liczba krawedzi 1500
Wagi od -100 do 1500
Wynik zmiesci sie w long int

Zadanie nalezy oddac najpozniej na laboratorium 19 marca godz. 17:30.
Rozwiazanie nalezy rowniez przeslac na adres franekg(at)mimuw.edu.pl