The first two responses in this thread gave you reliable answers (as have others): remote inverted canister or propane. Your budget is fine for most of them. Recapping:
Propane is great (close to -40) but the canisters are heavy (the common green “1 pound” Coleman tank weighs close to two pounds when full). Flame King sells a quarter-pound refillable tank, and Ultra Flame in Canada sells propane in lighter-weight canisters. You will need an adapter to use propane with most stoves (search “Coleman-to-Lindal adapter”).
Fire Maple makes some nice remote inverted canister stoves (look at their Polaris), as well as the Kovea Spider. BRS even makes a $25 remote inverted canister stove that will do the job, although it is two ounces heavier than Fire Maple or Kovea.
Combining propane with a remote canister stove would give you a more stable platform for cooking that will work in any temperature that you’re likely to want to.
However, whatever stove you have now will probably work long enough to boil water if you keep the canister warm (jacket, sleeping bag, Hothands, lighter). You can place the canister in a pan of water to keep it working for longer if necessary.