問題
$HOJ$国では駅1,駅2,...,駅$N$の$N$個の駅があります。
最初すべての駅はつながっていません。
提案は表でであらわされ、$C_{i,j}$は駅$i$から駅$j$の間に電車を開通させるときにかかるコストを表しています。
K君は提案の中からいくつか選び、できるだけ全体コストを抑えてすべての駅を行き来できるようにしたいと考えています。
すべての駅の行き来ができるようにするためにかかる全体コストの最小値を出力してください。全体コストとは開通させた電車のコストの総和です。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$C_{1,2}$ $C_{1,3}$ ... $C_{1,N}$
$C_{2,3}$ ... $C_{2,N}$
:
$C_{N-1,N}$
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 1100$
- $1 \leq C_{i,j} \leq 10^{9}$
- 入力はすべて整数
入出力例
入力例1
3 9 3 4
出力例1
7
入力例2
5 3 1 4 1 5 9 2 6 5 3
出力例2
7
※本来はNの上限を$2000$にするつもりでしたが、重すぎてHOJにアップロードできませんでした。なのでNの上限が$1100$になっています。