Миллиардер 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