  In this paper, we study the complete graph $K_n$ with n vertices, where we
attach an independent and identically distributed (i.i.d.) weight to each of
the n(n-1)/2 edges. We focus on the weight $W_n$ and the number of edges $H_n$
of the minimal weight path between vertex 1 and vertex n. It is shown in (Ann.
Appl. Probab. 22 (2012) 29-69) that when the weights on the edges are i.i.d.
with distribution equal to that of $E^s$, where $s>0$ is some parameter, and E
has an exponential distribution with mean 1, then $H_n$ is asymptotically
normal with asymptotic mean $s\log n$ and asymptotic variance $s^2\log n$. In
this paper, we analyze the situation when the weights have distribution
$E^{-s},s>0$, in which case the behavior of $H_n$ is markedly different as
$H_n$ is a tight sequence of random variables. More precisely, we use the
method of Stein-Chen for Poisson approximations to show that, for almost all
$s>0$, the hopcount $H_n$ converges in probability to the nearest integer of
s+1 greater than or equal to 2, and identify the limiting distribution of the
recentered and rescaled minimal weight. For a countable set of special s values
denoted by $\mathcal{S}=\{s_j\}_{j\geq2}$, the hopcount $H_n$ takes on the
values j and j+1 each with positive probability.
