1258 Agri-Net

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

問題

農夫ジョンは彼の街の町長に選ばれた！彼のキャンペーンの一つは地域のすべての農場をインターネットでつなぐことであった。彼はもちろんのことながらあなたの助けを必要としている。
農夫ジョンは高速インターネット通信を彼の農場に準備し、さらに彼のインターネット通信を他の農場にも使わせようとしている。コスト削減のため、彼は可能な限り少ない少ない光ファイバーで彼の農場と他の農場をつなげたい。
それぞれの農場を結ぶのに必要な光ファイバーの量のリストが与えられるので、あなたはすべてをつなぐために必要な光ファイバーの量の最小値を求めなければいけない。それぞれの農場は必ずその他の農場とパケットがどこかひとつの農場からほかの農場へ流れることができるようにつながれている。
いずれの２つの農場の距離も100000を超えない。

入力

入力はいくつかのケースを含む。それぞれのケースは、最初の行に農場の数N(3<=N<=100)を含む。続く行にはN×Nの行列が含まれ、それぞれの要素は農場から別の農場への距離を表している。つまり、N個の空白で区切られた整数がN行となっている。
また、それらの行は80文字の長さに規制されていて、いくつかの行は次の行に続く場合がある。もちろん対角線上は0となり、農場iからそれ自身への距離はこの問題に関与しない。

出力

それぞれのケースにつき、一つのそのケース全ての農場を結ぶために必要な光ファイバーの長さの最小値を表す整数を出力しなさい。

サンプル入力

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

サンプル出力

28

出典

USACO 102