  We introduce a novel multivariate approach for solving weighted parameterized
problems. In our model, given an instance of size $n$ of a minimization
(maximization) problem, and a parameter $W \geq 1$, we seek a solution of
weight at most (or at least) $W$. We use our general framework to obtain
efficient algorithms for such fundamental graph problems as Vertex Cover,
3-Hitting Set, Edge Dominating Set and Max Internal Out-Branching. The best
known algorithms for these problems admit running times of the form $c^W
n^{O(1)}$, for some constant $c>1$. We improve these running times to $c^s
n^{O(1)}$, where $s\leq W$ is the minimum size of a solution of weight at most
(at least) $W$. If no such solution exists, $s=\min\{W,m\}$, where $m$ is the
maximum size of a solution. Clearly, $s$ can be substantially smaller than $W$.
In particular, the running times of our algorithms are (almost) the same as the
best known $O^*$ running times for the unweighted variants. Thus, we solve the
weighted versions of
  * Vertex Cover in $1.381^s n^{O(1)}$ time and $n^{O(1)}$ space.
  * 3-Hitting Set in $2.168^s n^{O(1)}$ time and $n^{O(1)}$ space.
  * Edge Dominating Set in $2.315^s n^{O(1)}$ time and $n^{O(1)}$ space.
  * Max Internal Out-Branching in $6.855^s n^{O(1)}$ time and space.
  We further show that Weighted Vertex Cover and Weighted Edge Dominating Set
admit fast algorithms whose running times are of the form $c^t n^{O(1)}$, where
$t \leq s$ is the minimum size of a solution.
