import java.io.*;

public class GetLittleTree{
        public int dim = 0; //記錄圖中結點數
        public int[] tem; //用來暫時緩存圖中的數據
        public int[][] edge; //使用鄰接矩陣表示圖
        public int[][] tree; //用來存放最小生成數的鄰接矩陣
        public int[] count; //用來記錄取去結點
        public int cop = 1 ;//結點計數器
        StreamTokenizer st;
        FileOutputStream fw;
  public GetLittleTree()throws IOException ,FileNotFoundException{
    Reader r = new BufferedReader(new InputStreamReader(new FileInputStream("in.txt")));
    st = new StreamTokenizer(r);
    fw = new FileOutputStream("out.txt");
    st.nextToken();
    st.pushBack();
    st.nextToken();
    dim = (int) st.nval; //獲取圖中的結點數
    count = new int[dim];
    count[0] = 1; //對于邊割法可以任意選取初始點，不仿取第一個結點作為開始結點
    tem = new int[dim*dim];
    edge = new int[dim][dim];
    tree = new int[dim][dim];
	int acc = 0;
	int k = 0;
    while ((st.nextToken()) != st.TT_EOF) {
      st.pushBack();
      st.nextToken();
      tem[acc++] = (int) st.nval;
    }
    /*
     *將緩存在數組中的數據轉移到表示圖的二維數據結構中
     */
     for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
          edge[i][j] = tem[k++];
        }
     }//for
  }
/*
 *對于邊割法可以任意選取初始點，不仿取第一個結點作為開始結點
 *并采用冒泡法尋找最小的元素
 */
 public int getLittleValue(int[][] b,int[] count,int[][] tree)throws IOException{
   int recoder = 10000;
   int len = count.length;
   int iflag = 0;
   int jflag = 0;
   int flag = 1;
   for (int i = 0; i < len; i++) { //將count中記錄的所有記錄行，掃描一遍
     if (count[i] == 1) {
       for (int j = 1; j < len; j++) {
         if (count[j] == 1) { //如果count中記錄元素，說明此結點不在所選之中
           continue;
          } //if
         else { //冒泡法找最小元素
           if((recoder > b[i][j]) && (b[i][j] != 0)){
             recoder = b[i][j];
             iflag = i;
             jflag = j;
            }
         } //else
       } //for
     } //if
   } //for
   if(recoder == 10000){
           System.out.println("此圖不連通,沒有最小生成樹！");
           flag = 0;
   }
   cop++;
   count[jflag] = 1; //將最小元素結點記錄在count中
   tree[iflag][jflag] = recoder; //將結點連接的邊放在最小生成樹矩陣中
   tree[jflag][iflag] = recoder;//圖為對稱
   return flag;
 }
 public void getLittleTree()throws IOException{
	 while (cop != dim) {
       if(getLittleValue(edge, count, tree) == 1){
                   ;
           }
           else{
                   break;
           }
     }
	 if(cop == dim){
		 result();
	 }
 }
 public void result ()throws IOException ,FileNotFoundException{
     for (int i = 0; i < dim; i++) {
       for (int j = 0; j < dim; j++) {
         fw.write(Integer.toOctalString(tree[i][j]).getBytes("ISO-8859-1"));
		 fw.write(" ".getBytes());
	//	 bos.writeChars(" ");
		 System.out.print(tree[i][j]+" ");
       } //for
         fw.write("\n".getBytes());
		System.out.print("\n");
     } //for
	    fw.close();//關閉輸出流
   }
   /*
    * 測試結果是否正確
    */
   public static void main(String args[])throws IOException{
     GetLittleTree gt = new GetLittleTree();
     gt.getLittleTree(); 
  }
}