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 show by Aldous (1998) that the critical value of lambda is 1/e, below which the length is logarithmic and above which the length is linear. We show that at criticality the order of the length is (log n)^3...