Sachverhalt:
A.
P._ trat am 1. August 2011 in das von der Stiftung Alters- und Pflegeheim X._ betriebene Heim ein, während ihr Ehemann bis zu dessen Tod im August 2012 in der vormalig gemeinsamen Wohnung in der Stadt Zürich blieb. Mit Einspracheentscheid vom 11. Januar 2013 teilte das Amt für Zusatzleistungen zur AHV/IV der Stadt Zürich der Stiftung Alters- und Pflegeheim X._ mit, es übernehme ab 1. Januar 2013 die Pflegebeiträge für P._ nicht mehr.
B.
Hiegegen erhob die Stiftung Alters- und Pflegeheim X._ Beschwerde beim Sozialversicherungsgericht des Kantons Zürich. Dieses verneinte seine Zuständigkeit und trat auf das Rechtsmittel mit Beschluss vom 31. Mai 2013 nicht ein.
C.
Sowohl die Stiftung Alters- und Pflegeheim X._ (Verfahren 9C_582/2013) als auch die Stadt Zürich, Amt für Zusatzleistungen zur AHV/IV (Verfahren 9C_587/2013), erheben gegen den Nichteintretensbeschluss Beschwerde in öffentlich-rechtlichen Angelegenheiten.
Die Stadt Zürich schliesst sich der Beschwerde der Stiftung Alters- und Pflegeheim X._ an.
D.
Mit Entscheid vom heutigen Tag tritt das Bundesgericht auf die Beschwerde der Stadt Zürich (Verfahren 9C_587/2013) betreffend dieselbe Zuständigkeitsfrage zufolge Verspätung des Rechtsmittels nicht ein.
Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unter anderem zulässig gegen Entscheide, die das Verfahren abschliessen (Art. 90 BGG). Der vorinstanzliche Nichteintretensentscheid kann als Endentscheid im Sinne von Art. 91 BGG (Urteil 9C_740/2008 vom 10. Oktober 2008 E. 1) oder als - selbstständig eröffneter - Vor- oder Zwischenentscheid über die Zuständigkeit nach Art. 92 Abs. 1 BGG betrachtet werden. Die dagegen erhobene Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit zulässig (BGE 135 V 125 E. 1 S. 126).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann die Verletzung von Bundesrecht gerügt werden (Art. 95 lit. a BGG). Nicht in Art. 95 lit. c-e BGG genannte Quellen kantonalen Rechts werden vom Bundesgericht inhaltlich nur daraufhin überprüft, ob deren Anwendung zu einer Bundesrechtswidrigkeit führt. Im Vordergrund steht dabei eine Verletzung verfassungsmässiger Rechte (BGE 133 I 201 E. 1 S. 203 mit Hinweisen).
2.
Streitigkeiten nach Eintritt eines Leistungsfalles fallen in die Zuständigkeit der II. sozialrechtlichen Abteilung, wenn - allenfalls auch nur im Hintergrund - sozialversicherungsrechtliche Leistungen umstritten sind. Die kantonale Restfinanzierung der Pflegekosten gehört zu den sozialversicherungsrechtlichen Leistungen. Entsprechende Streitigkeiten fallen somit in die Zuständigkeit der II. sozialrechtlichen Abteilung, wenn, wie hier, ein Leistungsfall bereits eingetreten ist. Auf die Beschwerde kann eingetreten werden (BGE 138 V 377 E. 2.2 S. 379).
3.
Streitig ist die innerkantonale Zuständigkeit für die Beurteilung von strittiger Restfinanzierung der Pflegekosten gemäss Art. 25a Abs. 5 Satz 2 KVG.
3.1. Die Vorinstanz erwog, Art. 25a Abs. 5 KVG normiere die Restfinanzierung nicht inhaltlich, sondern sei nur eine Delegationsnorm, welche die Regelungskompetenz den Kantonen übertrage. Diese Kompetenz beinhalte sowohl die Regelung des inner-, wie auch des interkantonalen Verhältnisses, woran nichts ändere, dass die Kantone noch keine umfassende Regelung (Konkordat) erlassen hätten, vielmehr liege darin eine kantonalrechtliche Lücke.
Im Kanton Zürich enthielten weder das kantonale Pflegegesetz vom 27. September 2010 (LS 855.1) noch die Verordnung vom 22. November 2010 über die Pflegeversorgung (LS 855.11) verfahrensrechtliche Bestimmungen zur Restfinanzierung ungedeckter Pflegekosten nach Art. 25a Abs. 5 KVG. Das Bundesgesetz vom 6. Oktober 2000 über den Allgemeinen Teil des Sozialversicherungsrechts (ATSG; SR 830.1) werde in der regierungsrätlichen Weisung vom 28. April 2010 zum Pflegegesetz nicht erwähnt. Die Anwendbarkeit des ATSG ergebe sich weder direkt noch gestützt auf die Materialien. Selbst wenn das ATSG mangels kantonaler Verfahrensbestimmungen zu berücksichtigen wäre, käme lediglich eine Anwendung als subsidiäres kantonales Recht in Frage, ohne dass im kantonalen Recht (namentlich nicht im Einführungsgesetz vom 13. Juni 1999 zum Krankenversicherungsgesetz [EG KVG; LS 832.01]) für die Restfinanzierung der Pflegekosten die Zuständigkeit des Sozialversicherungsgerichts des Kantons Zürich statuiert werde. Ebenso wenig ergebe sich dessen Zuständigkeit aus § 3 des Gesetzes vom 7. März 1993 über das Sozialversicherungsgericht (GSVGer; LS 212.81). Die sich auf Art. 25a Abs. 5 Satz 2 KVG stützenden kantonalen Vorschriften seien autonomes kantonales Recht. Dass Art. 25a Abs. 5 Satz 2 KVG nicht im Ausnahmekatalog von Art. 1 Abs. 2 KVG figuriere, lasse nicht darauf schliessen, das ATSG wäre von Bundesrechts wegen auch auf autonomes kantonales Recht anwendbar, das basierend auf Art. 25a Abs. 5 Satz 2 KVG ergangen sei. Weil es sich im vorliegenden Fall um einen Streit zwischen einer Pflegeeinrichtung und einer Behörde handle, falle schliesslich die verfahrensrechtliche Erschwerung nicht ins Gewicht, welche bezogen auf natürliche versicherte Personen in BGE 138 V 377 ein Argument für die Zuständigkeit des kantonalen Versicherungsgerichts gewesen sei.
3.2. Die Beschwerdeführerin bringt vor, Art. 1 Abs. 2 KVG sei im Zuge der Neuordnung der Pflegefinanzierung nicht erweitert worden. Das ATSG sei folglich auch im Bereich der Restfinanzierung von Pflegekosten anzuwenden, woran nichts ändere, dass die Leistung nicht durch eine Sozialversicherung erbracht werde. Art. 25a Abs. 5 Satz 2 KVG stelle es den Kantonen nicht frei zu legiferieren, sondern belasse ihnen nur in eingeschränktem Mass Regelungskompetenz, namentlich hinsichtlich der Zuständigkeit für die Ausrichtung der Pflegebeiträge, und somit ausschliesslich für den Erlass von Ausführungsbestimmungen. Bei dem Art. 25a Abs. 5 KVG umsetzenden kantonalen Recht handle es sich nicht um autonomes kantonales Recht, sondern um unselbstständiges kantonales Ausführungsrecht, welches dem Bundessozialversicherungsrecht zuzuordnen sei. Damit fände das ATSG Anwendung. Im Übrigen sei nicht davon auszugehen, dass der kantonale Gesetzgeber einen von den anderen sozialversicherungsrechtlichen Ansprüchen abweichenden Verfahrensweg im Auge gehabt habe.
3.3. Die Stadt Zürich bringt inhaltlich nichts vor. Sie reicht aber einen - ebenfalls - die innerkantonale Zuständigkeit für die Beurteilung einer Pflegefinanzierungsstreitigkeit betreffenden Entscheid des Verwaltungsgerichts des Kantons Zürich vom 23. Oktober 2013 (Verfahren VB.2013.00200) ins Recht, mit welchem das kantonale Verwaltungsgericht entschied, solche Streitigkeiten fielen in den Zuständigkeitsbereich des kantonalen Sozialversicherungsgerichts, sowie eine Kopie der von ihr gegen den verwaltungsgerichtlichen Entscheid erhobenen Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 21. November 2013 (hängiges Verfahren 9C_849/2013).
4.
4.1. Gemäss Art. 25a Abs. 5 Satz 2 KVG ist die Legiferierungskompetenz der Kantone auf die Regelung der Restfinanzierung der Pflegekosten beschränkt. Allein Sache der Bundesgesetzgebung bleibt die abschliessende Normierung der Leistungen der obligatorischen Krankenversicherung. Aber auch der grundsätzliche Anspruch auf Übernahme der ungedeckten Pflegekosten durch die öffentliche Hand (Kanton oder Gemeinden) ist keine Leistung autonomen kantonalen Rechts, sondern ein bundesrechtlicher Anspruch, woran die den Kantonen in Art. 25a Abs. 5 Satz 2 KVG übertragene Zuständigkeit nichts ändert (vgl. BGE 138 I 410 E. 4.2 und 4.3 S. 418 f.). Davon scheint auch der kantonale Gesetzgeber auszugehen, spricht er doch in § 9 Pflegegesetz (Randtitel: "Pflichtleistungen") von der Gesamtheit der Pflegeleistungen gemäss Art. 25a Abs. 5 KVG. Diese Gesamtheit der Pflegeleistungen umfasst neben den Leistungen zu Lasten der Versicherer und zu Lasten der Versicherten auch die restlichen Kosten, welche von der Gemeinde zu tragen sind (§ 9 Abs. 4, § 10, § 13 Abs. 3 und § 15 Abs. 2 Pflegegesetz). Ob die kantonale Kompetenz auch das Verfahren umfasst, hat das Bundesgericht in BGE 138 V 377 E. 5.3 S. 382 offengelassen, unter Hinweis darauf, dass im Bundesgesetz vom 13. Juni 2008 über die Neuordnung der Pflegefinanzierung (AS 2009 3517 ff.) keine explizite Anwendbarkeitserklärung des ATSG erfolgte, weil diese für den Gesetzgeber selbstverständlich war. Auch wenn Art. 1 Abs. 2 KVG die Ausnahmen von der Anwendbarkeit des ATSG nicht abschliessend regelt, ist der im Zuge der Neuregelung der Pflegefinanzierung unverändert gebliebene gesetzliche Ausnahmekatalog mindestens ein Indiz, dass für den Gesetzgeber die Anwendbarkeit des ATSG auf Streitigkeiten über die Restfinanzierung evident war. Zum gleichen Schluss gelangte etwa auch der Vorstand der Schweizerischen Konferenz der kantonalen Gesundheitsdirektorinnen und -direktoren (GDK) in seinen am 22. Oktober 2009 verabschiedeten "Empfehlungen zur Umsetzung der Neuordnung der Pflegefinanzierung", worin er die im Rahmen von Art. 25a Abs. 5 KVG anerkannten und geleisteten Zahlungen als sozialversicherungsrechtliche Beiträge nach KVG bezeichnete, die in den Anwendungsbereich des ATSG fielen.
4.2. Das Bundesgericht hat in BGE 138 V 377 E. 5.6 S. 384 f. entschieden, das Verfahren gemäss ATSG finde auf Streitigkeiten über die Restfinanzierung von Pflegeleistungen jedenfalls dann Anwendung, wenn der kantonale Gesetzgeber keine oder keine abweichende Regelung getroffen hat. Daran ist festzuhalten. Während in BGE 138 V 377, den Kanton St. Gallen betreffend, keine kantonale Norm vorlag, indes aus den Materialien ein klarer gesetzgeberischer Wille hervorging, wonach es sich bei diesen Streitigkeiten um eine sozialversicherungsrechtliche Leistung handle und demzufolge das ATSG Anwendung finde, ist weder den zürcherischen Normen noch den einschlägigen kantonalen Materialien ein Hinweis auf das anwendbare Verfahrensrecht zu entnehmen. Auch in diesem Fall fehlender kantonaler Grundlagen ist das Verfahren gemäss ATSG anwendbar. Es ist kein Grund ersichtlich, weshalb die kantonalen Versicherungsgerichte für die Beurteilung von Ansprüchen gemäss Art. 25a Abs. 5 KVG nicht geeignet sein sollten.
Zudem ist Folgendes zu beachten: Nach dem Gesagten (vorangehende E. 2 und 4.1) sind die Ansprüche auf Übernahme der ungedeckten Pflegekosten sozialversicherungs- sowie bundesrechtlicher Natur. Gemäss Art. 1 lit. b ATSG finden auf Sozialversicherungsrecht des Bundes die verfahrensrechtlichen Bestimmungen des ATSG Anwendung. Das mit dem ATSG (unter anderem) verfolgte gesetzgeberische Ziel einer Verfahrensvereinheitlichung (Art. 1 lit. b ATSG) kann nur erreicht werden, wenn das einschlägige Verfahrensrecht möglichst umfassend und - vorbehältlich gesetzlich geregelter Ausnahmen - insbesondere für die Beurteilung bundessozialversicherungsrechtlicher Ansprüche angewendet wird. Nicht zuletzt führte es zu einem wenig wünschbaren, der Maxime der einheitlichen Anwendung des Bundesrechts widersprechenden Zustand, wenn für den gleichen (bundessozialversicherungsrechtlichen) Anspruch in gewissen Kantonen das ATSG als Bundesrecht, in anderen das ATSG als subsidiäres kantonales Recht und wieder in anderen Kantonen das ATSG überhaupt nicht zur Anwendung gelangte. Art. 25a Abs. 5 Satz 2 KVG enthält mit Bezug auf das Verfahrensrecht keinen (expliziten) Vorbehalt des Bundesgesetzgebers zu Gunsten des kantonalen Rechts (vielmehr ging der Gesetzgeber wohl selbstverständlich von der Anwendbarkeit des ATSG aus; E. 4.1 hievor).
5.
5.1. Im Kanton Zürich regeln weder das Pflegegesetz noch die zugehörige Verordnung das Verfahren bei Streitigkeiten über die Restfinanzierung von Pflegekosten noch lassen sich den Materialen Hinweise darauf entnehmen, der kantonale Gesetzgeber hätte eine vom ATSG abweichende Verfahrensordnung beabsichtigt (E. 3.1 hievor). Nach dem Gesagten findet damit das ATSG und finden insbesondere dessen Rechtspflegebestimmungen (Art. 56 ff. ATSG) Anwendung.
5.2. Nicht zuletzt sprechen auch spezifische kantonalrechtliche Praktikabilitätsgründe für die Anwendbarkeit des ATSG. Die Zuständigkeit für die Restfinanzierung fällt im Kanton Zürich in den kommunalen Kompetenzbereich (§ 21 Abs. 1 Pflegegesetz). Mangels Verfügungskompetenz einer Gemeinde gegenüber einer gemeindefremden öffentlich-rechtlichen oder einer privatrechtlichen Pflegeinstitution wäre die Anfechtung einer abgelehnten Übernahme ungedeckter Pflegebeiträge mittels Rekurs (§ 19 Abs. 1 lit. a in Verbindung mit § 19b Abs. 2 lit. c des kantonalen Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 [VRG; LS 175.2]) in diesen Fällen ausgeschlossen, und es müsste ein Klageverfahren vor Verwaltungsgericht als einziger Instanz angehoben werden (§ 81 lit. a VRG). Dass der kantonale Gesetzgeber für die Pflegefinanzierung unterschiedliche Rechtswege vorsehen wollte, je nachdem, ob sich eine Person in einer gemeindeeigenen öffentlich-rechtlichen Pflegeinstitution oder in einer auswärtigen Pflegeeinrichtung beziehungsweise in einer privatrechtlichen Institution befindet, ist nicht anzunehmen und liegt umso weniger auf der Hand, als das Pflegegesetz in § 9 Abs. 4 und 5 die Tragung der ungedeckten Pflegekosten detailliert regelt, während das Verfahrensrecht keinerlei Erwähnung fand.
5.3. Auf Streitigkeiten betreffend die Pflegefinanzierung zwischen der versicherten Person und dem Kanton gemäss Art. 25a Abs. 5 KVG gelangen somit auch im Kanton Zürich die (verfahrensrechtlichen) Bestimmungen des ATSG zur Anwendung. Gemäss dem in Art. 56 ff. ATSG vorgezeichneten Rechtsweg ist das kantonale Versicherungsgericht zuständig für die Beurteilung von Streitigkeiten über die Restfinanzierung von Pflegekosten. Die Sache ist an dieses zum materiellen Entscheid zurückzuweisen.
5.4. Anders ist die Rechtslage, wenn es nicht um einen konkreten Leistungsfall geht, sondern um den (grundsätzlichen) Umfang der (kantonalen) Mitfinanzierung von ausserkantonalen Wahlbehandlungen nach Art. 49a KVG. In einem solchen Streitfall handelt es sich um Abgeltung der stationären Leistungen bzw. um die künftige Praxis des Kantons bei der Anerkennung von Forderungen einer stationären Einrichtung. Der Anspruch eines Leistungserbringers gegen den Kanton auf anteilmässige Vergütung der stationären Behandlung lässt sich aus Art. 41 Abs. 1bis KVG nicht abstrakt, sondern nur anhand eines konkreten Falles ableiten. Damit geht es in der Sache um eine Tarifstreitigkeit zwischen Leistungserbringerin und Kanton, auch wenn Patienten davon indirekt betroffen sein können. Auf diese Streitigkeit sind die Bestimmungen des ATSG nach dem klaren Wortlaut von Art. 1 Abs. 2 lit. b KVG von vornherein nicht anwendbar. Dies steht im Einklang mit dem Grundsatz, wonach das ATSG primär auf das Verhältnis zwischen Versicherten und Versicherern zugeschnitten ist, und mit Art. 1 Abs. 2 KVG diejenigen Bereiche nicht unter das ATSG fallen, für welche das ATSG-Verfahren nicht geeignet ist (9C_905/2013 vom 4. Februar 2014 E. 3.1.2).
6.
Auf die Erhebung von Gerichtskosten wird umständehalber verzichtet (Art. 66 Abs. 1 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 31. Mai 2013 wird aufgehoben, und die Sache wird an das kantonale Gericht zurückgewiesen, damit es im Sinne der Erwägungen verfahre.
2.
Es werden keine Gerichtskosten erhoben.
3.
Die Beschwerdeführerin wird für das bundesgerichtliche Verfahren mit Fr. 2'800.- aus der Gerichtskasse entschädigt.
4.
Dieses Urteil wird den Parteien, P._, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 18. März 2014
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Die Gerichtsschreiberin: Bollinger Hammerle