Miliarder Christian poznał dziś algorytm Dijkstra z potencjałami Johnson. Spodobał mu się tak bardzo, że postanowił dodać potencjały do wszystkich swoich ulubionych grafów. Christian ma bardzo osobliwy gust — w swoim sekretnym pokoju przechowuje wyłącznie skierowane grafy ważone.

Przypomnijmy, jak działają potencjały. Każdemu wierzchołkowi $v$ przypisujemy potencjał: liczbę rzeczywistą $\varphi(v)$. Jeśli istniała krawędź z $u$ do $v$ o początkowej wadze $w$, jej nowa waga wynosi $w'=w-\varphi(v)+\varphi(u)$.

Siłę grafu definiujemy jako minimum wag jego krawędzi. Christian nie chce słabych grafów w swoim pokoju, więc zamierza dobrać potencjały tak, aby zmaksymalizować siłę grafu. Pomóż mu.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ ($2\le n\le1000$) i $m$ ($1\le m\le100\,000$), liczbę wierzchołków i krawędzi w grafie, który Christian lubi najbardziej. Każdy z następnych $m$ wierszy zawiera trzy liczby całkowite $u_i,v_i,w_i$ opisujące krawędź: odpowiednio jej początek, koniec i wagę ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).

Wyjście

Pierwszy wiersz musi zawierać maksymalną siłę grafu. Jeśli odpowiedź można uczynić dowolnie dużą, zamiast niej wypisz napis „+inf”.

Jeśli odpowiedź jest skończona, drugi wiersz musi zawierać $n$ liczb rzeczywistych: potencjały wierzchołków. Wartość bezwzględna każdej z nich nie może przekraczać $10^{10}$. Twoja odpowiedź musi różnić się zarówno od poprawnej odpowiedzi, jak i od odpowiedzi obliczonej na podstawie podanych potencjałów o nie więcej niż $10^{-5}$.

Przykład

Wejście 1

3 3
1 2 1
2 3 1
3 1 1

Wyjście 1

1.0
0.0 0.0 0.0

Wejście 2

2 1
1 2 1

Wyjście 2

+inf