億萬富翁 Christian 今天學到了帶 Johnson 勢函數的 Dijkstra 演算法。他非常喜歡這個演算法，決定給自己所有心愛的圖都加上勢。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