考虑带权的有向图 G=(V,E) 以及 w:E→R，每条边e=(i,j)(i≠j,i∈V,j∈V) 的权值定义为Wi,j，令 n=∣V| 。c=(c₁,c₂,⋯,c_k)(c_i∈V) 是 G中的一个圈当且仅当 (c_i,c_i+1)(1≤i<k)和 (c_k,c₁)都在 E中，这时称 k 为圈 c的长度。同时令 c_k+1=c₁ ​​ ，并定义圈 c=(c₁,c₂,⋯,c_k) 的平均值为：

即 c上所有边的权值的平均值。

令 μ∗(c)=min{μ(c)}为 G中所有圈 c 的平均值的最小值。现在的目标是：在给定了一个图 G=(V,E) 以及 w:E→R之后，请求出 G中所有圈 c的平均值的最小值 μ∗(c)=min{μ(c)}

第一行包含两个正整数 n 和 m，并用一个空格隔开，其中 n=∣V∣,m=∣E∣，分别表示图中有 n个顶点和 m条边；

接下来 m行，每行包含用空格隔开的三个数 i,j,w_i,j，表示有一条边 (i,j) 且该边的权值为 w_i,j ​​

输入数据保证图 G=(V,E)连通，存在圈且有一个点能到达其他所有点。

仅包含一个实数 μ∗=min{μ(c)}，要求输出到小数点后 8位

数据范围：

对于 20% 的数据，1≤n≤100,1≤m≤1000；

对于 40% 的数据，1≤n≤1000,1≤m≤5000；

对于 100% 的数据，1≤n≤3000,1≤m≤10⁴,∣w_i,j ∣≤10⁷。

输入保证 1≤i,j≤n