你们有 n 计算机被从 1 总计到 n 和你想要连接他们制造一个小当地的区域网络 （区域网络）.所有连接是双行道的.（哪一正在连接计算机 i 和 j 相同于连接计算机 j 和 i）连接计算机 i 和计算机 j 的费用是 cij .你由于一些特别的理由不能够连接计算机的一些双.你想要连接他们,以便每部计算机直接地或者间接地连接至任何其他的,而且你也想要尽可能少支付.
给予的 n 和每 cij ,找最廉宜的方法连接计算机.
输入
有多个测试情形.输入的第一条线包含一个完整的事物 T（T ＜=100),指出测试情形的数字.然后 T 测试情形而起.
每个测试情形的第一条线包含一个完整的事物 n .（1< n ＜=100)然后 n 排成一行追从,每个哪一个包含因空间而分开的 n 完整的事物.i－th 的 j－th 完整的事物排成一行在这些 n 线是 cij,指出连接计算机 i 和 j 的费用.（cij ＝ 0个方法你不能够连接他们）0