For a complete graph of size $n$, assign each edge an i.i.d.\ exponential variable with mean $n$. For $λ>0$, consider the length of the longest path whose average weight is at most $λ$. It was shown by Aldous (1998) that the length is of order $\log n$ for $λ< 1/\mathrm{e}$ and of order $n$ for $λ> 1/\mathrm{e}$. In this paper, we study the near-supercritical regime where $λ= \mathrm{e}^{-1} +η$ with $η>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η}$ and $n \mathrm{e}^{-c^*/\sqrtη}$. Our result corrects a non-rigorous prediction of Aldous (2005).