There is a way to transform the All Pairs Shortest Distances (APSD) problem where the edge lengths are integers with small (less than or equal to M) absolute value into a problem with edge lengths in {-1, 0, 1}. This transformation allows us to use the algorithms we developed earlier ([1]) and yields quite efficient algorithms. In this paper we give new improved algorithms for these problems. For n = \V\ the number of vertices, M the bound on edge length, and omega the exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSD(n, M) algorithm which runs in O(T(n, M)) time, where [GRAPHICS] 2. A undirected APSD(n, M) algorithm which runs in O(M(omega+1/2)n(omega) log(Mn)) time.