  Haj\'os conjectured in 1968 that every Eulerian \(n\)-vertex graph can be
decomposed into at most $\lfloor (n-1)/2\rfloor$ edge-disjoint cycles. This has
been confirmed for some special graph classes, but the general case remains
open. In a sequence of papers by Bienia and Meyniel (1986), Dean (1986), and
Bollob\'as and Scott (1996) it was analogously conjectured that every
\emph{directed} Eulerian graph can be decomposed into $O(n)$ cycles. In this
paper, we show that every directed Eulerian graph can be decomposed into $O(n
\log \Delta)$ disjoint cycles, thus making progress towards the conjecture by
Bollob\'as and Scott. Our approach is based on finding heavy cycles in certain
edge-weightings of directed graphs. As a further consequence of our techniques,
we prove that for every edge-weighted digraph in which every vertex has
out-weight at least $1$, there exists a cycle with weight at least $\Omega(\log
\log n/{\log n})$, thus resolving a question by Bollob\'as and Scott.

Combinatorics;Probability