U372912 恐怖分子

一个国家由 n 个城市组成，任意两个城市间都有一条双向的道路。如今，恐怖分子想要炸掉 其中的一些道路，使得这 n 个城市变得不再连通，也就是说，存在至少两个城市，它们之间 不可通过道路互相到达。要炸毁一条道路需要一定的代价。请你计算一下要使恐怖分子达到 它们的目的，所需要的最小总代价是多少

第一行为正整数 n (n ≤ 1000)，表示城市的个数，接下来的 n 行每行由 n 个 0~9 之间 的数字组成，数字之间没有空格或任何其他字符间隔，第 i 行的第 j 个数字表示要破坏城市 i 与城市 j 之间的道路所需要的代价。输入数据保证对于任意 i, j。第 i 行的第 j 个数字与 第 j 行的第 i 个数相等，且对于所有的 i，第 i 行的第 i 个数字都等于 0。

输出仅有一个整数，即要破坏这 n 个城市的连通性，所需要的最小