class Floyd {
   private int n;
   private int M[][];

   public Floyd (int towns, int map[][]) {
      n = towns;
      M = new int[n][n]; 

      // Form initial map M0 in M      
      for (int i=0; i<n; i++)
         for (int j=0; j<n; j++)
            M[i][j] = map[i][j];

      // Successively form maps M1, ..., Mn in M
      for (int k=0; k<n; k++)
         for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
               if (M[i][k]+M[k][j] < M[i][j])
                  M[i][j] = M[i][k]+M[k][j];
   }

   public int shortest (int town1, int town2) {
      return M[town1][town2];   
   }
}