原題來自：HNOI 2009

考慮帶權(quán)的有向圖 G=(V,E) 以及 w:E→R，每條邊e=(i,j)(i≠j,i∈V,j∈V)的權(quán)值定義為W_i,j，令 n=∣V|。c=(c1,c2,?,ck)(ci∈V) 是 G 中的一個圈當(dāng)且僅當(dāng) (c_i,c_i+1)(1≤i<k) 和 (c_k,c₁) 都在 E 中，這時稱 k 為圈 c 的長度。同時令 c_k+1=c₁ ，并定義圈 c=(c1,c2,?,ck) 的平均值為：


即 c 上所有邊的權(quán)值的平均值。

令 μ?(c)=min{μ(c)} 為 G 中所有圈 c 的平均值的最小值。現(xiàn)在的目標(biāo)是：在給定了一個圖 G=(V,E) 以及 w:E→R 之后，請求出 G 中所有圈 c 的平均值的最小值 μ?(c)=min{μ(c)}。

第一行包含兩個正整數(shù) n 和 m，并用一個空格隔開，其中 n=∣V∣,m=∣E∣，分別表示圖中有 n 個頂點和 m 條邊；

接下來 m 行，每行包含用空格隔開的三個數(shù) i,j,w_i,j ，表示有一條邊 (i,j) 且該邊的權(quán)值為 w_i,j 。

輸入數(shù)據(jù)保證圖 G=(V,E) 連通，存在圈且有一個點能到達(dá)其他所有點。

僅包含一個實數(shù) μ?=min{μ(c)}，要求輸出到小數(shù)點后 8 位。

數(shù)據(jù)范圍：

對于 20% 的數(shù)據(jù)，1≤n≤100,1≤m≤1000；

對于 40% 的數(shù)據(jù)，1≤n≤1000,1≤m≤5000；

對于 100% 的數(shù)據(jù)，1≤n≤3000,1≤m≤10⁴,∣w_i,j∣≤10⁷ 。

輸入保證 1≤i,j≤n。

信息學(xué)一本通 圖論