億万長者 Christian は今日、Johnson のポテンシャルを使う Dijkstra のアルゴリズムを学びました。とても気に入ったので、お気に入りのすべてのグラフにポテンシャルを加えることにしました。Christian の好みは非常に独特で、秘密の部屋には重み付き有向グラフしか置いていません。

ポテンシャルの仕組みを振り返りましょう。各頂点 $v$ には、実数 $\varphi(v)$ であるポテンシャルを割り当てます。元の重みが $w$ である $u$ から $v$ への辺があれば、その新しい重みは $w'=w-\varphi(v)+\varphi(u)$ となります。

グラフの強さを、その辺の重みの最小値と定義します。Christian は部屋に弱いグラフを置きたくないので、グラフの強さが最大になるようポテンシャルを選びたいと考えています。彼を手伝ってください。

入力

最初の行には、Christian のお気に入りのグラフの頂点数と辺数を表す二つの整数 $n$（$2\le n\le1000$）と $m$（$1\le m\le100\,000$）が与えられます。続く $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