int INF=1<<30;
int father[110];
int map[110][110], ans;
bool visite[110], circle[110];
int root;
int exist_circle()
{
     father[root]= root;
     for( int i= 1; i<= n; ++i )
     if( !circle[i] && i!= root )
     {
         father[i]= i; map[i][i]= INF;
         for( int j= 1; j<= n; ++j )
         if( !circle[j] && map[j][i]< map[father[i]][i] )
         father[i]= j;
     }
     int i;
     for( i= 1; i<= n; ++i )
     {
         if( circle[i] ) continue;
         memset( visite, false, sizeof(visite) );
         int j= i;
         while( !visite[j] ) {   visite[j]= true;   j= father[j];   }
         if( j== root ) continue;
         return j;
     }
     return -1;
}
void   update( int t )
{
     ans+= map[father[t]][t];
     for( int i= father[t]; i!= t; i= father[i] )
     {
         ans+= map[father[i]][i];
         circle[i]= true;
     }
     for( int i= 1; i<= n; ++i )
     if( !circle[i] && map[i][t]!= INF )
     map[i][t]-= map[father[t]][t];
     for( int j= father[t]; j!= t; j= father[j] )
         for( int i= 1; i<= n; ++i )
         {
             if( circle[i] ) continue;
             if( map[i][j]!= INF )
             map[i][t]= min( map[i][t], map[i][j]- map[father[j]][j] );
             map[t][i]= min( map[j][i], map[t][i] );
         }
}
void solve()
{
     memset( circle, false, sizeof(circle) );
     int j;
     while( ( j= exist_circle() )!= -1 ) update( j );
     for( j= 1; j<= n; ++j )
     if( j!= root && !circle[j] )
     ans+= map[father[j]][j];
}