31381번 - Potential well 스페셜 저지다국어

문제

Billionaire Christian has learned today about Dijkstra's algorithm with Johnson potentials. He liked it so much that he decided to add potentials to all of his favourite graphs.

Christian's tastes are very singular --- he keeps in his secret room only directed weighted graphs.

A little reminder about potentials: each vertex $v$ will be assigned with its potential $\phi(v)$. If there was an edge from $u$ to $v$ with initial weight $w$ then its new weight will be $w' = w - \phi(v) + \phi(u)$.

Strength of a graph is defined as a minimum of its edges weights.

Christian don't want weak graphs in his room, so he want to choose potentials in such way that its strength is maximized.

입력

First line contains two integers $n$ (2ドル \le n \le 10^3$) and $m$ (1ドル \le m \le 10^5$) --- number of vertices and edges in Christian's favourite graph. Next $m$ lines contain triples of integers $u_i,円 v_i,円 w_i$ (1ドル \le u_i,,円 v_i \le n,ドル $|w_i| \le 10^6$) --- $i$-th edge goes from $a_i$ to $b_i$ and has weight $w_i$.

출력

First line shoult contain maximum strength of the graph. If it is possible to make the answer infinitely big then output +inf instead.

If the answer is finite then second line should contain potentials of vertices. They shouldn't exceed 10ドル^{10}$ by absolute value. Your answer should differ from the correct one and also from the answer computed based on your potentials no more than 10ドル^{-5}$.

제한

힌트