类比 P1730 最小密度路径

现需求解 “最小密度环”，即 有向图环中的权值和除以边的数量 的最小值，且将点数 $n$ 开到 $10^3$，边数 $m$ 开到 $10^4$ 如果使用类似于 P1730 的 Floyd 变形就做不了了，那该如何做？