Before revision:  Furthermore, for any integer k \geq 1 we give an algorithmfor maintaining\tilde{O}, and |E|= n^{1+\Omega(1)}.
After revision:  Furthermore, for any integer k \geq 1 +\epsilon)-approximate shortest paths from a set of s sources in\tilde{O}, and |E|= n^{1+\Omega(1)}.