Sachverhalt: A. Mit Publikation im Amtsblatt des Kantons Graubünden Nr. 37 vom 12. September 2013 gab die Regierung des Kantons Graubünden bekannt, dass die 120 Mitglieder des Grossen Rats für die Amtsperiode 2014-2018 am 18. Mai 2014 gewählt werden. Gleichzeitig publizierte die Regierung die Zahl der von jedem der 39 Kreise zu wählenden Mitglieder des Grossen Rats. Die Gesamterneuerungswahl des Grossen Rats fand am 18. Mai 2014 statt (erster Wahlgang). Mit Beschwerde vom 19. Mai 2014 an den Grossen Rat machten 33 Privatpersonen geltend, das Wahlverfahren für die Gesamterneuerungswahl des Grossen Rats verletze Art. 34 Abs. 2 sowie Art. 8 Abs. 1 BV. Sie beantragten die Kassation der Ergebnisse der Grossratswahlen. Eventualiter sei auf eine Kassation der Wahlergebnisse zu verzichten und festzustellen, dass das Majorzwahlverfahren des Kantons Graubünden für die Wahl des Grossen Rats vor der Bundesverfassung nicht standhalte und damit verfassungswidrig sei. Die zuständigen Behörden des Kantons Graubünden seien im Sinne eines Appellentscheids aufzufordern, im Hinblick auf die nächste Wahl des Grossen Rats eine verfassungskonforme Wahlordnung zu schaffen. Am 26. Mai 2014 erklärten zwei von den 33 Personen, sie nähmen aufgrund ihrer Wahl in den Grossen Rat von der Beschwerde Abstand. In einzelnen Kreisen wurde am 15. Juni 2014 ein zweiter Wahlgang durchgeführt. In einem Kreis fand am 15. Juni 2014 eine Nachwahl und am 6. Juli 2014 ein zweiter Wahlgang statt. B. Der Grosse Rat trat mit Beschluss vom 27. August 2014 auf die Beschwerde vom 19. Mai 2014 nicht ein, weil er zu deren Behandlung nicht zuständig sei, und überwies die Sache dem Verwaltungsgericht des Kantons Graubünden zur Behandlung. Dieser Beschluss blieb unangefochten. Mit Teilurteil vom 30. September 2014 stellte das Verwaltungsgericht fest, es sei zur Beurteilung der Beschwerde vom 19. Mai 2014 zuständig, wobei es in den Erwägungen darauf hinwies, dass damit noch nichts zu den weiteren Prozessvoraussetzungen oder zu materiellen Fragen gesagt sei. Mit Urteil vom 17. Dezember 2015 trat das Verwaltungsgericht auf die Beschwerde vom 19. Mai 2014 nicht ein. C. Gegen das Urteil des Verwaltungsgerichts vom 17. Dezember 2015 haben 21 Privatpersonen, welche bereits im kantonalen Verfahren als Beschwerdeführer beteiligt waren, am 24. Februar 2016 Beschwerde ans Bundesgericht erhoben. Sie beantragen die Aufhebung des angefochtenen Entscheids. Von einer Rückweisung der Sache an die Vorinstanz sei abzusehen. Stattdessen sei festzustellen, dass das Bündner Majorzsystem für die Wahl des Grossen Rats Art. 8 und Art. 34 BV verletze. Die zuständigen Behörden des Kantons Graubünden seien im Sinne eines Appellentscheids aufzufordern, im Hinblick auf die nächste Wahl des Grossen Rats eine verfassungskonforme Wahlordnung zu schaffen. Die Vorinstanz beantragt unter Verweis auf den angefochtenen Entscheid, die Beschwerde sei abzuweisen, soweit darauf eingetreten werde. Der Grosse Rat beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Eventualiter sei die Sache zur materiellen Beurteilung an die Vorinstanz zurückzuweisen. Die Regierung liess sich nicht vernehmen. Mit Eingabe vom 11. Mai 2016 halten die Beschwerdeführer sinngemäss an ihrer Beschwerde fest.