Sachverhalt: A. Am 28. Oktober 2015 stellte A.A._ für sich und seine zwei Brüder B.A._ und C.A._, Gesamteigentümer von Parzelle Gbbl. Nr. 2428 in Films, beim Gemeindevorstand Flims das Gesuch um Einleitung eines Baubewilligungsverfahrens. Sie beantragten, es sei der gegenwärtige Eigentümer der Parzelle Gbbl. Nr. 2426, D._, in einem beschwerdefähigen Beschluss aufzufordern, innerhalb einer angemessenen, vom Gemeinderat anzusetzenden Frist nachträglich ein Bewilligungsgesuch für die 2014 und/oder 2015 bereits durchgeführten Veränderungen (Anlagen in Form von Bäumen, Pflanzen und Sträuchern) auf Parzelle Gbbl. Nr. 2426 einzureichen. Die Parzellen Gbbl. Nrn. 2426 und 2428 sind einzig durch die Via da Scheia voneinander getrennt. Das Gemeindebauamt Flims teilte A.A._ mit Schreiben vom 15. Dezember 2015 zusammenfassend mit, für das Pflanzen von Bäumen brauche es keine Baubewilligung. Die Bäume seien nach Rücksprache mit der Gemeinde gesetzt worden. Bei den relativ nahe zur Strasse gepflanzten Bäumen handle es sich um Legföhren, die eine maximale Höhe von ca. 3 m erreichten. Dagegen erhob A.A._ für sich und seine zwei Brüder am 11. Januar 2015 beim Bau-, Verkehrs- und Forstdepartement des Kantons Graubünden Rechtsverweigerungsbeschwerde. Sie stellten sich auf den Standpunkt, gestützt auf Art. 22 Abs. 1 RPG (SR 700) bestehe eine Baubewilligungspflicht. Insbesondere habe sich das Gemeindebauamt nicht mit der Problematik des Schattenwurfs und der dadurch verursachten Vereisung der Via da Scheia im Winter, der Gefahr des Stürzens der neu gepflanzten Bäume auf die Strasse, der Behinderung der Schneeräumung und der Verletzung von Abstandsvorschriften und Höhenbeschränkungen längs der Via da Scheia auseinandergesetzt. Zudem könnten Legföhren gemäss der einschlägigen botanischen Literatur viel höher als 3 m in die Höhe wachsen. Das kantonale Bau-, Verkehrs- und Forstdepartement überwies am 13. Januar 2016 die Angelegenheit an das gemäss kantonalem Recht zuständige Verwaltungsgericht des Kantons Graubünden. Am 25. Januar 2016 nahm D._ Stellung und hielt fest, im Frühjahr 2015 seien in Absprache mit dem Forstamt Flims auf der Parzelle Gbbl. Nr. 2426 neue Sträucher und Bäume gesetzt worden, ca. 35 Legföhren entlang der Strasse, eine Gruppe von sieben jungen Lärchen und eine Schwarzföhre. Die Neupflanzung sei Ersatz für eine frühere Bepflanzung, die durch Sturmschäden und eine Rodungsaktion der Gemeinde 2014 zerstört worden sei. Die frühere Bepflanzung habe aus ca. 35 rund 15 - 25 m hohen Fichten bestanden und sei zusätzlich von einer zweiten Reihe von Heckenpflanzen gesäumt worden. Bei der Neuanpflanzung seien die Grenzabstände eingehalten, und die Bäume seien in den gewachsenen Boden gesetzt worden, ohne Änderungen am Gelände. Die Gemeinde Flims beantragte in ihrer Vernehmlassung vom 1. Februar 2016 die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. 2014 seien auf der Parzelle Gbbl. Nr. 2426 durch das Forstamt Flims verschiedene Tannen und Laubbäume gefällt worden, weil diese den Verkehr auf der Via da Scheia insbesondere im Winter gefährdet hätten. Die Neuanpflanzung sei in Absprache mit dem Forstamt erfolgt. In weiteren Eingaben hielten die Verfahrensbeteiligten an ihren Standpunkten fest. Mit Urteil vom 10. Mai 2016 wies das Verwaltungsgericht die Beschwerde vom 11. Januar 2016 ab. B. Mit Eingabe vom 13. Juli 2016 führt A.A._ für sich und seine zwei Brüder Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht. Sie beantragen, das angefochtene Urteil des Verwaltungsgerichts sei aufzuheben, und das Bundesgericht habe die Bewilligungspflicht der neuen Pflanzungen (Bäume und Sträucher) auf dem Grundstück Gbbl. Nr. 2426 in Flims festzustellen. Eventualiter sei die Sache zur neuen Beurteilung im Sinne der Erwägungen des Bundesgerichts an die Vorinstanz zurückzuweisen. Die Vorinstanz beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Gemeinde Flims verzichtet auf eine Stellungnahme zur Beschwerde. D._ hat sich nicht vernehmen lassen. Der Beschwerdeführer hält an seinem Standpunkt und an seinen Anträgen fest.