  Consider the complete graph on $n$ vertices, with edge weights drawn
independently from the exponential distribution with unit mean. Janson showed
that the typical distance between two vertices scales as $\log{n}/n$, whereas
the diameter (maximum distance between any two vertices) scales as
$3\log{n}/n$. Bollob\'{a}s et al. showed that, for any fixed k, the weight of
the Steiner tree connecting $k$ typical vertices scales as $(k-1)\log{n}/n$,
which recovers Janson's result for $k=2$. We extend this result to show that
the worst case $k$-Steiner tree, over all choices of $k$ vertices, has weight
scaling as $(2k-1)\log{n}/n$ and finally, we generalise this result to Steiner
trees with a mixture of typical and worst case vertices.
