First, note that the expression for $K$ is a bit misleading as it includes costs for the roads $k_{i,j}$ with $2 \le i<j \le n$ that we are of course not going to build. So we should instead work with $K'=\sum_{i=1}^n \sum_{j=n+1}^{2n} k_{i,j}+\sum_{n+1 \le i<j \le 2n} k_{i,j} \le K$ which is exactly the sum of the weights of the $\frac{n(3n-1)}{2}$ that we could potentially want to build. Note that w.l.o.g. we build exactly $n$ of them, so the expression $\frac{2K'}{3n-1} \le \frac{2K}{3n-1}$ (which we will obtain as an upper bound) nicely expresses that we can choose $n$ streets with "not-more-than-average" costs (and this is clearly optimal if all the streets are equally expensive). But of course we can not just build the $n$ cheapest streets, so we need to be a bit more clever. Indeed, the claim will follow immediately if we can partition the $\frac{n(3n-1)}{2}$ into groups of at least $n$ streets each, such that if we build any $n$ streets from any one of the groups, we will obtain a connection between all cities. Indeed, in that case, there will be a group which has "not-more-than-average" costs on average, and then we can just build the $n$ cheapest streets from this group. So from now on we can completely ignore the costs and we are left with a completely graph-theoretical question of partitioning the streets as above. The key for the construction will be the following well-known fact (sometimes known as the Walecki decomposition): If $m$ is odd, then the complete graph $K_m$ can be partitioned into $\frac{m-1}{2}$ Hamiltonian circles. By deleting one vertex, we see that if $m$ is even, then $K_m$ can be partitioned into $\frac{m}{2}$ Hamiltonian paths. Now first suppose that $n$ is even. Apply the fact above to the graph on the $n+1$ vertices $1,n+1,\dots,2n$. We then choose the groups to be the $n+1$ edges from each such Hamiltonian circle and the remaining groups are just $\{((i,n+1),\dots,(i,2n)\}$ with $2 \le i \le n$. This clearly works. For $n$ odd, we again consider the $n+1$ vertices $1,n+1,\dots,2n$ and use the partition into Hamiltonian paths of length $n$ for our groups. Again, we can just choose $\{(i,n+1),\dots,(i,2n)\}$ with $2 \le i \le n$ as the remaining groups.