Мільярдер Christian сьогодні дізнався про алгоритм Dijkstra з потенціалами Johnson. Він йому так сподобався, що Christian вирішив додати потенціали до всіх своїх улюблених графів. Смаки Christian дуже своєрідні — у своїй таємній кімнаті він тримає лише орієнтовані зважені графи.

Нагадаємо, як працюють потенціали. Кожній вершині $v$ призначається потенціал — дійсне число $\varphi(v)$. Якщо було ребро з $u$ до $v$ з початковою вагою $w$, його нова вага дорівнюватиме $w'=w-\varphi(v)+\varphi(u)$.

Сила графа визначається як мінімум ваг його ребер. Christian не хоче слабких графів у своїй кімнаті, тому бажає вибрати потенціали так, щоб максимізувати силу графа. Допоможіть йому.

Вхідні дані

Перший рядок містить два цілі числа $n$ ($2\le n\le1000$) і $m$ ($1\le m\le100\,000$) — кількість вершин і ребер в улюбленому графі Christian. Кожен із наступних $m$ рядків містить три цілі числа $u_i,v_i,w_i$, що описують ребро: його початок, кінець і вагу відповідно ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).

Вихідні дані

Перший рядок має містити максимальну силу графа. Якщо відповідь можна зробити як завгодно великою, натомість виведіть рядок «+inf».

Якщо відповідь скінченна, другий рядок має містити $n$ дійсних чисел — потенціали вершин. Модуль кожного з них не повинен перевищувати $10^{10}$. Ваша відповідь має відрізнятися і від правильної відповіді, і від відповіді, обчисленої на основі ваших потенціалів, не більше ніж на $10^{-5}$.

Приклади

Вхідні дані 1

3 3
1 2 1
2 3 1
3 1 1

Вихідні дані 1

1.0
0.0 0.0 0.0

Вхідні дані 2

2 1
1 2 1

Вихідні дані 2

+inf