  We present an $m^{4/3+o(1)}\log W$-time algorithm for solving the minimum
cost flow problem in graphs with unit capacity, where $W$ is the maximum
absolute value of any edge weight. For sparse graphs, this improves over the
best known running time for this problem and, by well-known reductions, also
implies improved running times for the shortest path problem with negative
weights, minimum cost bipartite $\boldsymbol{\mathit{b}}$-matching when
$\|\boldsymbol{\mathit{b}}\|_1 = O(m)$, and recovers the running time of the
currently fastest algorithm for maximum flow in graphs with unit capacities
(Liu-Sidford, 2020).
  Our algorithm relies on developing an interior point method-based framework
which acts on the space of circulations in the underlying graph. From the
combinatorial point of view, this framework can be viewed as iteratively
improving the cost of a suboptimal solution by pushing flow around
circulations. These circulations are derived by computing a regularized version
of the standard Newton step, which is partially inspired by previous work on
the unit-capacity maximum flow problem (Liu-Sidford, 2019), and subsequently
refined based on the very recent progress on this problem (Liu-Sidford, 2020).
The resulting step problem can then be computed efficiently using the recent
work on $\ell_p$-norm minimizing flows (Kyng-Peng-Sachdeva-Wang, 2019). We
obtain our faster algorithm by combining this new step primitive with a
customized preconditioning method, which aims to ensure that the graph on which
these circulations are computed has sufficiently large conductance.
