Sachverhalt: A. Der 1978 geborene M._ meldete sich im Januar 2002 in der Gemeinde Y._ (GR) an, nachdem er seinen Aufenthalt in der Psychiatrischen Klinik abgebrochen und sich in der Stadt A._ abgemeldet hatte. Seit dem 3. Februar 2002 hielt er sich mit Unterbrüchen in verschiedenen Stationen der Psychiatrischen Dienste auf. Die Amtsvormundschaft, welche mit Beschluss vom 14. Juni 2004 für M._ eine kombinierte Beiratschaft errichtet hatte, meldete diesen am 12. Oktober 2004 in der Gemeinde X._ an. Diese stellte am 9. November 2004 den Schriftenempfangsschein aus und bescheinigte am 19. April 2007 den gesetzlichen Wohnsitz in X._ seit dem Zuzug von Y._ am 11. Oktober 2004. Seit Juni 2008 lebt M._ im Rahmen eines begleiteten Wohnens in einem Wohnheim der Stadt Z._. Mit Schreiben vom 6. Februar 2009 ersuchte sein Beirat die Stadt X._ um Übernahme von ausstehenden Rechnungen in Höhe von insgesamt rund Fr. 17'000.-. Diese trat am 26. Februar 2009 auf das Gesuch mit der Begründung nicht ein, M._ verzeichne in der Gemeinde X._ keinen Wohnsitz. B. Dagegen erhob M._ Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Dieses hiess die Beschwerde mit Entscheid vom 17. November 2009 gut und wies die Stadt X._ an, das Unterstützungsgesuch materiell zu behandeln. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt die Stadt X._ beantragen, in Aufhebung des angefochtenen Entscheids sei zu erkennen, dass M._ nie in der Stadt X._ Wohnsitz hatte. Das Verwaltungsgericht und M._ schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten ist. Denselben Antrag stellen auch die Stadt Z._ und die Gemeinde Y._ als Beigeladene. 