マス \((x_i, y_i)\) に石を置くことを、\(N\) 頂点のグラフにおいて有向辺 \((x_i, y_i)\) を張ることに対応させます。

すると、目標の状態は「全ての頂点において入次数と出次数が同じ」です。

有向辺 \((x_1, y_1)\) を張るという条件の元では、これを含む重みの和が最小のサイクルを求めれば良く、頂点 \(y_1\) から頂点 \(x_1\) への最短経路を求めれば良く、これはダイクストラ法で解くことができます。

よってこの問題は \(O(N+M\log M)\) で解くことができます。