  We study computing {\em all-pairs shortest paths} (APSP) on distributed
networks (the CONGEST model). The goal is for every node in the (weighted)
network to know the distance from every other node using communication. The
problem admits $(1+o(1))$-approximation $\tilde O(n)$-time algorithms
~\cite{LenzenP-podc15,Nanongkai-STOC14}, which are matched with $\tilde
\Omega(n)$-time lower
bounds~\cite{Nanongkai-STOC14,LenzenP_stoc13,FrischknechtHW12}\footnote{$\tilde
\Theta$, $\tilde O$ and $\tilde \Omega$ hide polylogarithmic factors. Note that
the lower bounds also hold even in the unweighted case and in the weighted case
with polynomial approximation ratios.}. No $\omega(n)$ lower bound or $o(m)$
upper bound were known for exact computation.
  In this paper, we present an $\tilde O(n^{5/4})$-time randomized (Las Vegas)
algorithm for exact weighted APSP; this provides the first improvement over the
naive $O(m)$-time algorithm when the network is not so sparse. Our result also
holds for the case where edge weights are {\em asymmetric} (a.k.a. the directed
case where communication is bidirectional). Our techniques also yield an
$\tilde O(n^{3/4}k^{1/2}+n)$-time algorithm for the {\em $k$-source shortest
paths} problem where we want every node to know distances from $k$ sources;
this improves Elkin's recent bound~\cite{Elkin-STOC17} when $k=\tilde
\omega(n^{1/4})$.
