AT_agc036_d [AGC036D] Negative Cycle

[problemUrl]: https://atcoder.jp/contests/agc036/tasks/agc036_d $ N $ 頂点からなる重み付き有向グラフがあり、頂点には $ 0 $ から $ N-1 $ までの番号がついています。 最初、このグラフには $ N-1 $ 本の辺があります。 このうち $ i $ 番目 ($ 0\ \leq\ i\ \leq\ N-2 $) の辺は、 頂点 $ i $ から頂点 $ i+1 $ へ向かう重さ $ 0 $ の辺です。 すぬけさんはこれから、全ての $ i,j $ ($ 0\ \leq\ i,j\ \leq\ N-1,\ i\ \neq\ j $) について、新たに辺 $ (i\ →\ j) $ を追加する操作を行います。 辺の重さは、$ i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_{0,1} $ $ A_{0,2} $ $ A_{0,3} $ $ \cdots $ $ A_{0,N-1} $ $ A_{1,0} $ $ A_{1,2} $ $ A_{1,3} $ $ \cdots $ $ A_{1,N-1} $ $ A_{2,0} $ $ A_{2,1} $ $ A_{2,3} $ $ \cdots $ $ A_{2,N-1} $ $ \vdots $ $ A_{N-1,0} $ $ A_{N-1,1} $ $ A_{N-1,2} $ $ \cdots $ $ A_{N-1,N-2} $

りんごくんが目的を達成するために必要なコストの総和の最小値を出力せよ。

### 制約 - $ 3\ \leq\ N\ \leq\ 500 $ - $ 1\ \leq\ A_{i,j}\ \leq\ 10^9 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 すぬけさんが追加した辺 $ (0\ →\ 1) $ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $ 2 $ で、これが最小です。 ### Sample Explanation 2 すぬけさんが追加した辺 $ (1\ →\ 2) $ と $ (3\ →\ 0) $ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $ 1+1=2 $ で、これが最小です。