Sachverhalt: Sachverhalt: A. Im Dezember 2003 erteilte die Gemeinde Schiers dem Ehepaar X._ die Baubewilligung für den Um- und Ausbau ihres Wohnhauses mit 2 Wohnungen auf der Parzelle Nr. 212. Als Auflage verfügte die Gemeinde, vor Baubeginn sei der Nachweis über die Bereitstellung zweier Autoabstellplätze zu erbringen. Das bisherige Wohnhaus verfügte über keine Parkplätze. Die Bauherrschaft erhob gegen diese Auflage am 7. Januar 2004 Rekurs an das Verwaltungsgericht des Kantons Graubünden. In der Folge hob die Gemeinde am 9. Februar 2004 die umstrittene Auflage auf und verfügte dafür eine Parkplatzersatzabgabe von Fr. 4'500.-- pro Wohnung, das heisst insgesamt Fr. 9'000.--. Dagegen rekurrierte die Bauherrschaft erneut beim Verwaltungsgericht. Die Bauherrschaft erhob gegen diese Auflage am 7. Januar 2004 Rekurs an das Verwaltungsgericht des Kantons Graubünden. In der Folge hob die Gemeinde am 9. Februar 2004 die umstrittene Auflage auf und verfügte dafür eine Parkplatzersatzabgabe von Fr. 4'500.-- pro Wohnung, das heisst insgesamt Fr. 9'000.--. Dagegen rekurrierte die Bauherrschaft erneut beim Verwaltungsgericht. B. Das Verwaltungsgericht vereinigte die beiden Rekursverfahren, soweit das erste nicht gegenstandslos geworden war, und führte einen Augenschein durch. Mit Urteil vom 25. Mai 2004 wies es die Rekurse ab, soweit sie nicht gegenstandslos geworden waren. B. Das Verwaltungsgericht vereinigte die beiden Rekursverfahren, soweit das erste nicht gegenstandslos geworden war, und führte einen Augenschein durch. Mit Urteil vom 25. Mai 2004 wies es die Rekurse ab, soweit sie nicht gegenstandslos geworden waren. C. Mit staatsrechtlicher Beschwerde vom 13. September 2004 beantragt das Ehepaar X._, der Entscheid des Verwaltungsgerichts vom 25. Mai 2004 sowie die Verfügung der Gemeinde Schiers vom 9. Februar 2004 seien aufzuheben. Das Verwaltungsgericht und die Gemeinde Schiers beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Verwaltungsgericht und die Gemeinde Schiers beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. D. Mit Verfügung des Präsidenten der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 7. Oktober 2004 wurde der Beschwerde aufschiebende Wirkung zuerkannt.