今天下午一场结束了的比赛的题。

有一个 $n$ 行 $m$ 列的带权无向网格图，求出一个边集 $S$，使得删去 $S$ 中的所有边后点 $(1,1)$ 和点 $(n,m)$ 不连通，求 $S$ 中每条边边权和的最小值。

$n,m \leq 1000$