El multimillonario Christian ha aprendido hoy el algoritmo de Dijkstra con los potenciales de Johnson. Le ha gustado tanto que ha decidido añadir potenciales a todos sus grafos favoritos. Los gustos de Christian son muy peculiares: en su habitación secreta solo guarda grafos dirigidos ponderados.
Recordemos cómo funcionan los potenciales. A cada vértice $v$ se le asigna un potencial: un número real $\varphi(v)$. Si había una arista de $u$ a $v$ con peso inicial $w$, su nuevo peso será $w'=w-\varphi(v)+\varphi(u)$.
La fuerza de un grafo se define como el mínimo de los pesos de sus aristas. Christian no quiere grafos débiles en su habitación, así que desea elegir los potenciales de forma que la fuerza del grafo sea máxima. Ayúdalo.
Entrada
La primera línea contiene dos enteros $n$ ($2\le n\le1000$) y $m$ ($1\le m\le100\,000$), el número de vértices y aristas del grafo favorito de Christian. Cada una de las siguientes $m$ líneas contiene tres enteros $u_i,v_i,w_i$ que describen una arista: su origen, destino y peso, respectivamente ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).
Salida
La primera línea debe contener la fuerza máxima del grafo. Si es posible hacer que la respuesta sea infinitamente grande, imprime en su lugar la cadena «+inf».
Si la respuesta es finita, la segunda línea debe contener $n$ números reales: los potenciales de los vértices. El valor absoluto de cada uno no debe superar $10^{10}$. Tu respuesta debe diferir tanto de la respuesta correcta como de la calculada a partir de tus potenciales en no más de $10^{-5}$.
Ejemplos
Entrada 1
3 3 1 2 1 2 3 1 3 1 1
Salida 1
1.0 0.0 0.0 0.0
Entrada 2
2 1 1 2 1
Salida 2
+inf