from time import clock
import sys


def Find_min(Vertex,mark,queue):
     
     minvalue=10000     
     index=-1
     ver=0
     
     for i in range(0,len(queue)):
          xn=queue[i]

          for j in range(1,len(Vertex[xn])):  ## edge no
               
               if( int(Vertex[xn][j]) < minvalue and mark[j-1]==0 and int(Vertex[xn][j])!=0 ):
                    minvalue=int(Vertex[xn][j])
                    index=j
                    ver=xn

     
     return minvalue,index,ver



def Prim_MST():

     try:
          
          InFile=open('in19_1.txt','r')
          OutFile=open('out_11_sec19_1.txt','w') 
          
          start=clock()
          Edges=InFile.readline().split(" ")
          
          mark=[0]*len(Edges)
          queue=[]
          
          Vertex=[]
          MSTEdges=[]
          for i in range(0,7):
               Vertex.append(InFile.readline().split(" "))    

## START  
          Totalcost=0
          queue.append(0)
          while( len(MSTEdges) !=len(Vertex)-1):              

               minvalue,indexedg,xn=Find_min(Vertex,mark,queue)
               
               j=0
               while(int(Vertex[j][indexedg])!=minvalue or xn==j):                               
                    j+=1
                    
               queue.append(j)
               mark[indexedg-1]=1
               MSTEdges.append(Edges[indexedg-1])
               Totalcost+=minvalue

          for i in range(0,len(MSTEdges)-1):
               OutFile.write(str(MSTEdges[i])+",")

          OutFile.write(str(MSTEdges[len(MSTEdges)-1]))           
                           
          
## END           
          OutFile.write("\nTotal Cost is : "+str(Totalcost))                    
          OutFile.write("\nTotal Excution Time : "+str(clock()-start))                    
          
          memUsed = sys.getsizeof(InFile) + sys.getsizeof(OutFile)+ sys.getsizeof(start)+ sys.getsizeof(Vertex)+ sys.getsizeof(Edges)+ sys.getsizeof(MSTEdges)+ sys.getsizeof(mark)+ sys.getsizeof(queue)+ sys.getsizeof(minvalue)+ sys.getsizeof(indexedg)
          OutFile.write("\nMemory used : "+str(memUsed)+" Bytes")        


          InFile.close()
          OutFile.close()
          
          print "Check Your Output File : out_11_19_1.txt is Generated"

     except ValueError:

          print "Check Your Output File Cant Not Generated",ValueError
          InFile.close()
          OutFile.close()



Prim_MST()