  For a complete graph of size $n$, assign each edge an i.i.d.\ exponential
variable with mean $n$. For $\lambda>0$, consider the length of the longest
path whose average weight is at most $\lambda$. It was shown by Aldous (1998)
that the length is of order $\log n$ for $\lambda < 1/\mathrm{e}$ and of order
$n$ for $\lambda > 1/\mathrm{e}$. In this paper, we study the
near-supercritical regime where $\lambda = \mathrm{e}^{-1} +\eta$ with $\eta>0$
a small fixed number. We show that there exist two absolute constants $c^*,
C^*>0$ such that with high probability the length is in between $n
\mathrm{e}^{-C^*/\sqrt{\eta}}$ and $n \mathrm{e}^{-c^*/\sqrt{\eta}}$. Our
result corrects a non-rigorous prediction of Aldous (2005).
