Yes the cost of the spell is to sacrifice and the cost has to be paid before the spell chooses a target.
This is incorrect. Costs are paid AFTER declaring targets. Relevant rules sections below:
601.2. To cast a spell is to take it from where it is (usually the hand), put it on the stack, and pay its
costs, so that it will eventually resolve and have its effect. Casting a spell follows the steps listed
below, in order.
601.2c The player announces his or her choice of an appropriate player, object, or zone for each
target the spell requires.
601.2g The player pays the total cost in any order.
This means you cannot bring back the same Wurmcoil Engine you sacrifice with Trash for Treasure.
