億萬富翁 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