Sachverhalt:
A.
Am Samstag, 20. Dezember 2014, ab ca. 14.20 Uhr verteilte B._, Präsident des Vereins A._, auf dem Trottoir vor einem Modegeschäft in St. Gallen Flugblätter gegen "Pelz-Tierquälerei". Rund zehn Minuten nach Beginn der Flugblattaktion wies er sich auf Verlangen von Polizeibeamten hin aus. Die Polizei beobachtete in der Folge das Geschehen während etwa vierzig Minuten und führte mit dem anwesenden Rechtsanwalt von B._, Rolf W. Rempfler, Verhandlungen. Ausserdem wurde C._, der die Geschehnisse vor Ort von Anfang an auf Video aufgenommen hatte, ebenfalls polizeilich kontrolliert und aufgefordert, seine Videokamera auszuschalten. Um ca. 15 Uhr verlangte die Polizei von B._, das Verteilen der Flugblätter einzustellen. Da er dieser Aufforderung trotz Androhung einer Ungehorsamsstrafe nicht nachkam, verbrachte sie ihn gegen seinen Willen in ein Polizeifahrzeug und daraufhin in das Polizeigebäude. Vor der Abführung nahm die Polizei B._ die verbliebenen Flugblätter weg. Nach einer Besprechung im Polizeigebäude, bei der auch Rechtsanwalt Rolf W. Rempfler anwesend war, entliess sie ihn nach ca. einer halben Stunde wieder.
Mit Eingabe vom 27. Februar 2015 erhoben B._, der Verein A._ und C._ Beschwerde und stellten diverse Feststellungsbegehren betreffend die Flugblatt-Verteilaktion vom 20. Dezember 2014. Die Direktion Soziales und Sicherheit der Stadt St. Gallen wies die Beschwerde mit Beschluss vom 24. Februar 2017 ab. Einen dagegen erhobenen Rekurs wies das Sicherheits- und Justizdepartement (SJD) des Kantons St. Gallen mit Entscheid vom 16. April 2018 ebenfalls ab.
In der Folge gelangten B._, der Verein A._ und C._ an das Verwaltungsgericht des Kantons St. Gallen. Dieses hiess ihr Rechtsmittel mit Entscheid vom 10. Dezember 2018 teilweise gut. Es hob den Entscheid des SJD auf und stellte fest, das Verbot der Verteilung von Flugblättern, deren Beschlagnahme, die Verbringung auf den Polizeiposten und die Hinderung am Filmen des Geschehens sei verfassungswidrig gewesen (Dispositiv-Ziffer 1). Die Kosten des Beschwerdeverfahrens von Fr. 2'000.-- und die Kosten des Rekursverfahrens von Fr. 1'500.-- auferlegte es zu einem Fünftel B._, dem Verein A._ und C._ sowie zu vier Fünfteln dem SJD (Dispositiv-Ziffer 2). Weiter ordnete es an, das SJD habe B._, den Verein A._ und C._ für das Rekursverfahren mit Fr. 900.-- (einschliesslich Barauslagen und zuzüglich 8 % Mehrwertsteuer) und für das Beschwerdeverfahren mit Fr. 1'872.-- (zuzüglich 7,7 % Mehrwertsteuer) zu entschädigen (Dispositiv-Ziffer 3).
B.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 25. Januar 2019 beantragen B._, der Verein A._ und C._, Dispositiv-Ziffer 3 des Entscheids des Verwaltungsgerichts sei teilweise aufzuheben und die Sache zur neuen Festlegung der Parteientschädigung für das Rekursverfahren unter Berücksichtigung der Kostennote vom 31. Juli 2017 an das Verwaltungsgericht zurückzuweisen. Eventualiter sei die Parteientschädigung für das Rekursverfahren vom Bundesgericht selbst festzulegen.
Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde. Die Gemeinde St. Gallen hat sich nicht vernehmen lassen.

Erwägungen:
1.
Angefochten ist ein Entscheid über die Entschädigungsfolgen in einem Verfahren, das im Hauptpunkt eine Angelegenheit des öffentlichen Rechts betrifft (<ref-law>; vgl. <ref-ruling> E. 1.1 S. 160; Urteil 2C_1054/2017 vom 15. Mai 2018 E. 1.1; je mit Hinweisen). Der angefochtene Entscheid stammt von einer letzten kantonalen Instanz (<ref-law>) und schliesst das Verfahren ab (<ref-law>). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen, werden von der Entschädigungsregelung im angefochtenen Entscheid besonders berührt und haben insofern ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf das Rechtsmittel ist einzutreten.
2.
2.1. Die Beschwerdeführer rügen eine Verletzung ihres Anspruchs auf rechtliches Gehör. Das Verwaltungsgericht habe bei der Festlegung der Parteientschädigung für das Rekursverfahren die in den Akten befindliche Honorarnote vom 31. Juli 2017 nicht berücksichtigt. Es sei von einer ungekürzten Entschädigung im Umfang von Fr. 1'500.-- ausgegangen, während in der Honorarnote Fr. 8'050.-- ausgewiesen worden seien. Gemäss der kantonalen Praxis müsse das Gericht eine Abweichung von einer eingereichten Honorarnote begründen.
2.2. Ein Gericht ist gestützt auf den Anspruch auf rechtliches Gehör (<ref-law>) nicht immer gehalten, seinen Entscheid über die Höhe der Parteientschädigung zu begründen. Besteht ein Tarif oder eine gesetzliche Regel, die Minimal- und Maximalbeträge festhalten, so muss das Gericht seinen Entscheid nur begründen, wenn es diese Grenzen überschreitet oder wenn die betroffene Partei besondere Umstände geltend macht oder schliesslich dann, wenn das Gericht von einer von der betreffenden Partei eingereichten Kostennote abweicht und - ungeachtet einer bestehenden Praxis - eine geringere als die übliche Entschädigung zuspricht (<ref-ruling> E. 5.1 S. 504; Urteile 5A_932/2016 vom 24. Juli 2017 E. 2.1.1; 1B_328/2019 vom 17. Juli 2019 E. 4.1; 2D_35/2016 vom 21. April 2017 E. 3.1; je mit Hinweisen). Eine Pflicht zur Begründung besteht zudem dann, wenn die Kosten- und Entschädigungsfolgen den eigentlichen Verfahrensgegenstand bilden, was im Verfahren vor Verwaltungsgericht allerdings nicht zutraf (Urteil 2D_35/2016 vom 21. April 2017 E. 3.1).
2.3. Das Verwaltungsgericht setzte sich mit der Kostennote der Beschwerdeführer, welche diese im Verfahren vor dem SJD eingereicht hatten, nicht auseinander. Indessen verwies es auf den anwendbaren Kostenrahmen und die gesetzlichen Kriterien, nach denen das Grundhonorar zu bemessen ist (vgl. im Einzelnen E. 3.3 hiernach). Dass es in Missachtung einer bestehenden Praxis eine geringere als die übliche Entschädigung zugesprochen hätte, indem es von einem ungekürzten Honorar von Fr. 1'500.-- für das Verfahren vor dem SJD ausging, machen die Beschwerdeführer nicht geltend. Die angeführte Begründung genügt deshalb den bundesrechtlichen Anforderungen. Die Rüge der Verletzung des rechtlichen Gehörs ist unbegründet.
3.
3.1. Die Höhe der Parteientschädigung bemisst sich nach kantonalem Recht, dessen Anwendung vom Bundesgericht nur daraufhin überprüft werden kann, ob damit Bundesrecht, namentlich das Willkürverbot (<ref-law>), verletzt wird. Willkür in der Rechtsanwendung liegt vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft; dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht; zudem ist erforderlich, dass der Entscheid nicht nur in der Begründung, sondern auch im Ergebnis willkürlich ist (<ref-ruling> E. 4.2 S. 516 mit Hinweisen).
3.2. Die Beschwerdeführer legen dar, dass die Parteientschädigung gestützt auf das kantonale Recht allermindestens zwischen Fr. 5'000.-- und Fr. 6'000.-- betragen müsse. Sie behaupten zwar nicht explizit, der angefochtene Entscheid sei willkürlich, aus ihrer Kritik geht allerdings sinngemäss hervor, dass sie ihn als nicht mehr haltbar erachten.
Konkret bringen sie vor, dass der Entscheid der Direktion Soziales und Sicherheit der Stadt St. Gallen ausserordentlich kurz gewesen sei, weshalb es einer viel eingehenderen Auseinandersetzung mit der Sache durch ihren Rechtsvertreter bedurft habe. Dieser habe sich mit Fragen des gesteigerten Gemeingebrauchs, der Bewilligungspflicht sowie mit zahlreichen Grundrechtsbeschränkungen auseinandersetzen und zudem das Polizeireglement der Stadt St. Gallen auslegen müssen. Die Direktion Soziales und Sicherheit habe behauptet, ihr Rechtsvertreter sei über die Verhaftung vorgängig orientiert worden. Deshalb habe dieser diverse Videoaufnahmen, die insgesamt mehrere Stunden gedauert hätten, zu analysieren, auszuwerten und in den Rekurs einzubauen gehabt. Er habe sie - also die Beschwerdeführer - zur Flugblatt-Verteilaktion begleitet und vor Ort eine Eskalation zu verhindern versucht. Weil die Streitsache zudem für den Beschwerdeführer 2 besonders emotional und wichtig gewesen sei, seien zahlreiche, teils sehr zeitaufwändige Telefonate notwendig gewesen. Schliesslich sei eine Replik zu verfassen gewesen. Bei einem Stundenansatz von Fr. 250.-- gemäss Art. 24 der kantonalen Honorarordnung entspreche eine Parteientschädigung von Fr. 1'500.-- lediglich sechs Stunden Arbeit, was dem erforderlichen Aufwand nicht gerecht werde.
3.3. Die kantonale Honorarordnung für Rechtsanwälte und Rechtsagenten vom 22. April 1994 (sGS 963.75; im Folgenden: HonO) in der vorliegend anwendbaren Fassung (Stand: 9. Dezember 2010) sieht in Art. 13 ff. verschiedene Formen der Honorarbemessung vor: das Honorar nach Streitwert (Art. 13-18 HonO), die Honorarpauschale (Art. 19-22 HonO) und das Honorar nach Zeitaufwand (Art. 23-24 HonO). Für die Verwaltungsrechtspflege ist laut den vorinstanzlichen Ausführungen die Form der Honorarpauschale vorgesehen. Diese beträgt gemäss Art. 22 Abs. 1 lit. a HonO in Verfahren vor Verwaltungsbehörden Fr. 500.-- bis Fr. 6'000.--, wobei nach Abs. 2 für ein aussergewöhnlich kompliziertes Verfahren das Honorar bis zum Doppelten erhöht werden kann. Art. 19 HonO sieht weiter vor, dass innerhalb des für eine Pauschale gesetzten Rahmens das Grundhonorar nach den besonderen Umständen, namentlich nach Art und Umfang der Bemühungen, der Schwierigkeit des Falles und den wirtschaftlichen Verhältnissen der Beteiligten, bemessen wird.
Wenn die Beschwerdeführer geltend machen, eine Parteientschädigung von Fr. 1'500.-- entspreche bei einem Stundenansatz von Fr. 250.-- gemäss Art. 24 HonO lediglich 6 Stunden Arbeit, übersehen sie, dass Art. 24 HonO auf das Honorar nach Zeitaufwand anwendbar ist, nicht aber auf die Honorarpauschale. Dies ergibt sich nach dem Ausgeführten aus der Gesetzessystematik. Es besteht somit in der Verwaltungsrechtspflege kein gesetzlicher Anspruch auf einen Stundenansatz von Fr. 250.--.
3.4. Das Bundesgericht hat zudem festgehalten, dass die Parteientschädigung regelmässig nicht sämtliche erforderlichen Kosten decken muss, sondern nur einen Teil des nötigen Prozessaufwands. Bei der Frage, wie gross der Kostenanteil ist, den eine entschädigungsberechtigte Partei selber zu tragen hat, steht der Entscheidinstanz ein grosses Ermessen zu (Urteile 2D_35/2016 vom 21. April 2017 E. 6.2; 2C_172/2016 vom 16. August 2016 E. 4.5 mit Hinweisen). Bei Entschädigungen, die sich am Streitwert bemessen, sind gemäss dieser Rechtsprechung weiter gewisse Pauschalisierungen zulässig, sofern die Parteientschädigung nicht ausserhalb jedes vernünftigen Verhältnisses zur Wichtigkeit und Schwierigkeit der Sache sowie zu der damit für den Rechtsvertreter verbundenen Verantwortung und der von ihm in gebotener Weise aufgewendeten Zeit steht. Nicht mehr haltbar und damit willkürlich ist es insbesondere, wenn nur mehr symbolische Entschädigungen ausgerichtet werden, die den konkreten Verhältnissen in keiner Weise gerecht werden (a.a.O., E. 4.4 mit Hinweisen). Diese Erwägungen lassen sich auch auf Honorarpauschalen übertragen.
Der Rekurs an das SJD erforderte einigen Aufwand. Wie die Beschwerdeführer zu Recht vorbringen, hatte sich ihr Rechtsvertreter insbesondere mit Fragen des gesteigerten Gemeingebrauchs bzw. der Bewilligungspflicht, der Tragweite der Meinungsäusserungsfreiheit und der persönlichen Freiheit sowie mit dem kommunalen Polizeireglement vom 16. November 2004 und dem kantonalen Polizeigesetz vom 10. April 1980 (PG; sGS 451.1) zu befassen. Nicht einsichtig ist dagegen, weshalb Videoaufnahmen von mehreren Stunden Dauer ausgewertet werden mussten, da die Polizei gemäss den vorinstanzlichen Feststellungen bereits nach 40 Minuten intervenierte und das Ausschalten der Videokamera verlangte. Dasselbe gilt für den Umstand, dass die Angelegenheit für den Beschwerdeführer 2 besonders emotional und wichtig gewesen war. Schliesslich kann angesichts der in Art. 19 HonO aufgezählten Bemessungskriterien auch nicht beanstandet werden, wenn eine Rechtsmittelbehörde bei der Festlegung der Parteientschädigung unberücksichtigt lässt, dass der Rechtsvertreter die betroffene Partei bereits vor Erlass des angefochtenen Entscheids begleitet oder berät. Die Beschwerdeführer zeigen denn auch den Zusammenhang dieser Bemühungen mit dem Rekursverfahren nicht auf.
Trotz diesen teilweise nicht überzeugenden Argumenten der Beschwerdeführer erweist sich eine (ungekürzte) Parteientschädigung von Fr. 1'500.-- als ausgesprochen tief. Sie liegt im untersten Drittel des Entschädigungsrahmens von Fr. 500.-- bis Fr. 6'000.--, der für nicht aussergewöhnlich komplizierte Verfahren im Sinne von Art. 22 Abs. 2 HonO gilt. Angesichts des grossen Ermessensspielraums, welcher der Entscheidinstanz in diesem Zusammenhang zukommt und angesichts des Umstands, dass von Bundesrechts wegen die Parteientschädigung nicht sämtliche erforderlichen Kosten decken muss, erscheint sie allerdings nicht geradezu als willkürlich. Sie liegt jedoch am untersten Rand dessen, was mit Blick auf die Wichtigkeit und Schwierigkeit der Sache sowie die damit für den Rechtsvertreter verbundenen Verantwortung und die von ihm in gebotener Weise aufgewendete Zeit noch als vertretbar angesehen werden kann.
4.
Die Beschwerde ist aus diesen Erwägungen abzuweisen.
Bei diesem Verfahrensausgang sind die Kosten des bundesgerichtlichen Verfahrens den Beschwerdeführern aufzuerlegen (<ref-law>). Eine Parteientschädigung ist nicht zuzusprechen (Art. 68 Abs. 1-3 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3.
Es wird keine Parteientschädigung zugesprochen.
4.
Dieses Urteil wird den Beschwerdeführern, der Politischen Gemeinde St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen, Abteilung III, schriftlich mitgeteilt.
Lausanne, 31. Dezember 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Dold