In 1997 Klavzar and Gutman suggested a generalization of the Wiener index to vertex-weighted graphs. We minimize the Wiener index over the set of trees with the given vertex weights' and degrees' sequences and show an optimal tree to be the, so-called, Huffman tree built in a bottom-up manner by sequentially connecting vertices of the least weights.