#include<stdio.h>
int num;
int s[8],dist[8];
int d[8][8];
int cost[8][8]={{0,0,0,0,0,0,0,0},
{0,0,20,50,30,1000,1000,1000},
{0,1000,0,25,1000,1000,70,1000},
{0,1000,1000,0,40,25,50,1000},
{0,1000,1000,1000,0,55,1000,1000},
{0,1000,1000,1000,1000,0,10,70},
{0,1000,1000,1000,1000,1000,0,50},
{0,1000,1000,1000,1000,1000,1000,0}};
void init(){
     
     int i=0,j=0;
     for(i=1;i<=7;i++){                                
     for(j=1;j<=7;j++){
   d[i][j]=1;                   
      }    
     s[i]=0;                                        /*表示第i個接點沒有找到最短路徑*/
     dist[i]=cost[1][i];
 }
} 
void find(){
     int k=0;
     int i=0;
     int j=0;
     int m=0;
  s[1]=1;
  dist[1]=0;
  for(k=2;k<=7;k++){
  for(num=2000,i=2;i<=7;i++){              /*NUM便于每次開始時候都能比較*/
   if(s[i]==0)                          /*在還沒有找到最短路徑的接點中找距離最近的接點*/
    if(dist[i]<=num){
     num=dist[i];
     j=i;                         /*用J記錄距離最近的接點*/ 
    }
  }
  s[j]=1;                                   
  for(m=2;m<=7;m++){                         /*將已經找到的點加入記錄其路徑的數組*/
   if(d[j][m]==1){
    d[j][m]=j;
       break;
   }
  }
  for(i=2;i<=7;i++){                         
   if(s[i]==0){
    if(dist[i]>dist[j]+cost[j][i]){     /*每找到一個新接點如果其他最短路徑要修改，則改變他們的路徑長，以及其路徑*/
     dist[i]=dist[j]+cost[j][i];       /*修改到已經找到的集合的最短距離*/
     for(m=2;m<=7;m++)               /*修改其路徑*/
d[i][m]=d[j][m];            /*路徑改為剛找到的接點的路徑*/
    }
   }
  }
 }
 }  
          
          
void print(){
        int i=0;
        int j=0;
      for(i=1;i<=7;i++){                               /*輸出其路徑長，路徑*/
  printf("%d:  %d",i,dist[i]);
  for(j=1;j<=7;j++){
   printf("  %d",d[i][j]);
   if(d[i][j+1]==d[i][j+2])
    break;
  }
  printf("\n");
 }
 }            
 
int main()
{
 int a;
 init();
    find();
    print();
    a=getchar();
while(a!=EOF)
    a=getchar();
 return 1;
}