Der Milliardär Christian hat heute den Dijkstra-Algorithmus mit Johnson-Potentialen kennengelernt. Er war so begeistert, dass er all seinen Lieblingsgraphen Potentiale hinzufügen möchte. Christians Geschmack ist sehr eigenwillig: In seinem geheimen Zimmer bewahrt er nur gerichtete gewichtete Graphen auf.

Erinnern wir uns an die Funktionsweise von Potentialen. Jedem Knoten $v$ wird ein Potential zugewiesen: eine reelle Zahl $\varphi(v)$. Gab es eine Kante von $u$ nach $v$ mit ursprünglichem Gewicht $w$, so ist ihr neues Gewicht $w'=w-\varphi(v)+\varphi(u)$.

Die Stärke eines Graphen ist als das Minimum seiner Kantengewichte definiert. Christian möchte keine schwachen Graphen in seinem Zimmer haben. Daher möchte er die Potentiale so wählen, dass die Stärke des Graphen maximiert wird. Hilf ihm dabei.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ ($2\le n\le1000$) und $m$ ($1\le m\le100\,000$), die Anzahl der Knoten und Kanten in Christians Lieblingsgraphen. Jede der folgenden $m$ Zeilen enthält drei ganze Zahlen $u_i,v_i,w_i$, die eine Kante beschreiben: ihren Startknoten, Endknoten und ihr Gewicht, in dieser Reihenfolge ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).

Ausgabe

Die erste Zeile muss die größtmögliche Stärke des Graphen enthalten. Falls die Antwort beliebig groß werden kann, gib stattdessen die Zeichenfolge „+inf“ aus.

Ist die Antwort endlich, muss die zweite Zeile $n$ reelle Zahlen enthalten: die Potentiale der Knoten. Ihr Betrag darf jeweils $10^{10}$ nicht überschreiten. Deine Antwort darf sowohl von der korrekten Antwort als auch von der aus deinen Potentialen berechneten Antwort um höchstens $10^{-5}$ abweichen.

Beispiele

Eingabe 1

3 3
1 2 1
2 3 1
3 1 1

Ausgabe 1

1.0
0.0 0.0 0.0

Eingabe 2

2 1
1 2 1

Ausgabe 2

+inf