For a simple undirected connected graph G the Wiener index WI(G) is calculated as a half of the sum of elements of its distance matrix D(G). WI(G) is one of the most renowned graph indices widely used in mathematical chemistry, quantitative structure-property relation (QSPR) studies, and network analysis. In 1997 Klavzar and Gutman defined the Wiener index for vertex-weighted graphs as a quadratic form VWWI(G, mu) = 1/2*mu'*D(G)*mu, where mu is the vector of positive vertex weights. VWWI generalizes WI and is closely connected to spectral properties of the graph. We minimize VWWI over the set of trees with the given vertex weights' and degrees' sequences and show the optimal tree to be the, so-called, generalized Huffman tree built in a bottom-up manner by sequentially connecting vertices of the least weights to vertices of the least degree. Chemical trees are constructed, which minimize the Wiener index over all chemical trees with given vertex weights. It is also conjectured that the tree with given vertex weights' and degrees' sequences that maximizes VWWI is a “reversed” Huffman tree, which is built by sequentially connecting the heaviest vertices to vertices with the biggest degree. Several applications are discussed. Firstly, we find isomers of simple alcohols with extremal normal boiling point by minimizing the linear combination of VWWI and vertex-degree-based graph indices. Secondly, we suggest a lower bound of the routing (communication) tree cost.