The scala map data-structures can be pretty costly and inefficient.  Instead you could use an array containing the distances and then maintain a global map (shared by broadcast variable) with the mapping from vertex id to index in the array.  This should also reduce the memory overhead substantially since each vertex will not need to maintain its own locally Map data structure.