Sachverhalt: Sachverhalt: A. Im Kanton Basel-Stadt ist die Bestattung für alle verstorbenen Personen, die im Zeitpunkt ihres Ablebens im Kantonsgebiet wohnhaft gewesen sind, unentgeltlich (§ 3 in Verbindung mit § 14 Abs. 1 des kantonalen Gesetzes vom 9. Juli 1931 betreffend die Bestattungen). Die Leistungen bei unentgeltlicher Bestattung umfassen gemäss § 15 des Gesetzes u. a. die Lieferung eines einfachen Sarges (inkl. Einsargung) und eines einfachen Leichenhemdes (lit. a) sowie die Überführung der verstorbenen Person auf einen Friedhof im Kanton Basel-Stadt (lit. b). Gemäss Statistik des Baudepartementes des Kantons Basel-Stadt (Abteilung Stadtgärtnerei und Friedhöfe, im Folgenden: Baudepartement) wurden in den Jahren 1997 bis 2001 pro Jahr je zwischen 1553 und 2040 Einheitssärge unentgeltlich abgegeben; dies bei ungefähr 2'400 Todesfällen pro Jahr. Für eine Einsargung und einen Transport bezahlte das Baudepartement bisher Fr. 565.-- oder Fr. 585.-- an eines der sechs zugelassenen Bestattungsunternehmen. Gemäss Statistik des Baudepartementes des Kantons Basel-Stadt (Abteilung Stadtgärtnerei und Friedhöfe, im Folgenden: Baudepartement) wurden in den Jahren 1997 bis 2001 pro Jahr je zwischen 1553 und 2040 Einheitssärge unentgeltlich abgegeben; dies bei ungefähr 2'400 Todesfällen pro Jahr. Für eine Einsargung und einen Transport bezahlte das Baudepartement bisher Fr. 565.-- oder Fr. 585.-- an eines der sechs zugelassenen Bestattungsunternehmen. B. Am 17. August 2002 schrieb das Baudepartement zwei Dienstleistungen (Vertrag A und Vertrag B) im Bestattungswesen (Verrichtungen der Bestattungsunternehmungen im Zusammenhang mit Ansprüchen auf unentgeltliche Bestattung) zur Submission aus. Beim Vertrag A geht es um Einsargungen und Leichentransporte zum Friedhof auf Veranlassung von berechtigten Personen oder des Zivilstandsamtes, wobei - unter der Voraussetzung, dass das zweitplatzierte Los weniger als 30 % teurer als das günstigste sein müsste - die Aufteilung auf maximal zwei Lose vorgesehen war; beim Vertrag B geht es um Einsargungen im Institut für Pathologie auf Veranlassung dieses Instituts. Als Verfahrensart wurde das offene Verfahren gemäss § 12 lit. a des kantonalen Gesetzes vom 20. Mai 1999 über öffentliche Beschaffungen (Beschaffungsgesetz) gewählt. Neben verschiedenen, ausdrücklich genannten Anforderungen an die Anbieter (u.a. die Verpflichtung, den ausgeschriebenen Dienstleistungsauftrag selbst auszuführen sowie die Verpflichtung, die Gesamtarbeitsverträge bzw. die orts- und branchenüblichen Arbeitsbedingungen einzuhalten) wurde als einziges Zuschlagskriterium der Preis (100 %) genannt. Als Verfahrensart wurde das offene Verfahren gemäss § 12 lit. a des kantonalen Gesetzes vom 20. Mai 1999 über öffentliche Beschaffungen (Beschaffungsgesetz) gewählt. Neben verschiedenen, ausdrücklich genannten Anforderungen an die Anbieter (u.a. die Verpflichtung, den ausgeschriebenen Dienstleistungsauftrag selbst auszuführen sowie die Verpflichtung, die Gesamtarbeitsverträge bzw. die orts- und branchenüblichen Arbeitsbedingungen einzuhalten) wurde als einziges Zuschlagskriterium der Preis (100 %) genannt. C. Die zu einer Bietergemeinschaft zusammengeschlossenen Bestattungsunternehmungen A._, B._, C._, und D._, reichten für beide ausgeschriebenen Aufträge je ein Angebot ein (Fr. 585.-- bzw. Fr. 405.-- für den Vertrag A, Fr. 85.-- für den Vertrag B). Ebenfalls Angebote eingereicht hatten das Bestattungsinstitut Z._ (Deutschland), für den Vertrag A (Fr. 257.-- bzw. Fr. 157.--), eine weitere Bietergemeinschaft (bestehend aus dem Bestattungsinstitut P._ und der Q._ Bestattungen) für den Vertrag B (Fr. 55.--), und das Bestattungsinstitut M._ für beide Verträge (Fr. 240.65 bzw. 147.85/A sowie Fr. 56.50/B). Nach der Offertöffnung äusserten die zur ersterwähnten Bietergemeinschaft zusammengeschlossenen Unternehmungen am 29. Oktober 2002 dem Baudepartement gegenüber Bedenken gegenüber einzelnen Mitbietern, welche sich unlauterer Methoden bedient haben könnten. Das Baudepartement orientierte mit Schreiben vom 26. November 2002 darüber, dass die "aufgeworfenen Vermutungen/Fragen soweit erforderlich im Rahmen der Vergabe geprüft" würden. Am 10. Dezember 2002 erteilte das Baudepartement den Zuschlag für den Vertrag A an das Beerdigungsinstitut M._ (zum Preis von Fr. 240.65 pro Bestattung bei Todesfällen mit Anspruch auf unentgeltliche Transporte bzw. von Fr. 147.85 pro Bestattung für Fälle ohne derartigen Transportanspruch). Für den Vertrag B erhielt die Arbeitsgemeinschaft Bestattungsinstitut P._/Q._ Bestattungen den Zuschlag zum Preis von Fr. 55.-- pro Bestattung. Die Firma Z._ (D) hatte die Vergabebehörde vom Verfahren ausgeschlossen, weil diese Unternehmung die verlangten Nachweise nicht beigebracht habe. Am 10. Dezember 2002 erteilte das Baudepartement den Zuschlag für den Vertrag A an das Beerdigungsinstitut M._ (zum Preis von Fr. 240.65 pro Bestattung bei Todesfällen mit Anspruch auf unentgeltliche Transporte bzw. von Fr. 147.85 pro Bestattung für Fälle ohne derartigen Transportanspruch). Für den Vertrag B erhielt die Arbeitsgemeinschaft Bestattungsinstitut P._/Q._ Bestattungen den Zuschlag zum Preis von Fr. 55.-- pro Bestattung. Die Firma Z._ (D) hatte die Vergabebehörde vom Verfahren ausgeschlossen, weil diese Unternehmung die verlangten Nachweise nicht beigebracht habe. D. Gegen diese Zuschlagsverfügungen bzw. gegen ein Schreiben vom 23. Dezember 2002, in welchem das Baudepartement den Zuschlag ergänzend begründete, gelangte die Bietergemeinschaft A._ und Mitbeteiligte an das Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht). Sie machte im Wesentlichen geltend, die berücksichtigten Angebote seien bei weitem nicht kostendeckend und verstiessen gegen das kantonale Beschaffungsgesetz (§ 8 lit. f und i). Am 30. April 2004 wies das Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) die bei ihm erhobenen Rekurse ab. Sein begündetes Urteil versandte es am 7. September 2004. Am 30. April 2004 wies das Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) die bei ihm erhobenen Rekurse ab. Sein begündetes Urteil versandte es am 7. September 2004. E. Mit Eingabe vom 8. Oktober 2004 führen die zur Bietergemeinschaft A._ und Mitbeteiligte zusammengeschlossenen Unternehmungen staatsrechtliche Beschwerde beim Bundesgericht mit den Anträgen, das Urteil des Appellationsgerichts Basel-Stadt vom 30. April 2004 aufzuheben und die Sache zur Neubeurteilung an die "Vorinstanz" zurückzuweisen. Das Beerdigungsinstitut M._ beantragt, die Beschwerde abzuweisen. Die Arbeitsgemeinschaft Bestattungsinstitut P._ und Q._ Bestattungen hat sich nicht vernehmen lassen. Das Baudepartement des Kantons Basel-Stadt schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das Appellationsgericht des Kantons Basel-Stadt beantragt Abweisung der Beschwerde. Das Beerdigungsinstitut M._ beantragt, die Beschwerde abzuweisen. Die Arbeitsgemeinschaft Bestattungsinstitut P._ und Q._ Bestattungen hat sich nicht vernehmen lassen. Das Baudepartement des Kantons Basel-Stadt schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das Appellationsgericht des Kantons Basel-Stadt beantragt Abweisung der Beschwerde. F. Mit Verfügung vom 3. November 2004 hat der Abteilungspräsident das gleichzeitig mit der Beschwerdeeinreichung gestellte Gesuch um aufschiebende Wirkung abgewiesen. 