O multimilionário Christian aprendeu hoje o algoritmo de Dijkstra com os potenciais de Johnson. Gostou tanto que decidiu adicionar potenciais a todos os seus grafos favoritos. Os gostos de Christian são muito peculiares: no seu quarto secreto só guarda grafos dirigidos ponderados.

Recordemos como funcionam os potenciais. A cada vértice $v$ é atribuído um potencial: um número real $\varphi(v)$. Se existia uma aresta de $u$ para $v$ com peso inicial $w$, o seu novo peso será $w'=w-\varphi(v)+\varphi(u)$.

A força de um grafo é definida como o mínimo dos pesos das suas arestas. Christian não quer grafos fracos no seu quarto, por isso quer escolher os potenciais de forma a maximizar a força do grafo. Ajuda-o.

Entrada

A primeira linha contém dois inteiros $n$ ($2\le n\le1000$) e $m$ ($1\le m\le100\,000$), o número de vértices e arestas do grafo favorito de Christian. Cada uma das $m$ linhas seguintes contém três inteiros $u_i,v_i,w_i$ que descrevem uma aresta: a sua origem, destino e peso, respetivamente ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).

Saída

A primeira linha deve conter a força máxima do grafo. Se for possível tornar a resposta infinitamente grande, escreve a cadeia «+inf» em vez disso.

Se a resposta for finita, a segunda linha deve conter $n$ números reais: os potenciais dos vértices. O valor absoluto de cada um não pode exceder $10^{10}$. A tua resposta não pode diferir da correta, nem da resposta calculada a partir dos teus potenciais, em mais de $10^{-5}$.

Exemplos

Entrada 1

3 3
1 2 1
2 3 1
3 1 1

Saída 1

1.0
0.0 0.0 0.0

Entrada 2

2 1
1 2 1

Saída 2

+inf