Summary: S. Klavžar and I. Gutman [Discrete Appl. Math. 80, No. 1, 73–81 (1997; Zbl 0889.05046)] 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.