Sachverhalt:
A.
A.A._ (1972; Serbe) war in Mazedonien vom 27. März 1992 bis 10. Mai 2004 mit B.A._ (1971; Mazedonierin) verheiratet. Sie haben zwei Kinder (1992 und 1994). Am 30. Oktober 2005 heiratete A.A._ eine in der Schweiz niederlassungsberechtigte Serbin (1957). Am 28. Januar 2006 reiste A.A._ in die Schweiz ein. In der Folge erhielt er eine Aufenthaltsbewilligung und am 8. März 2011 eine Niederlassungsbewilligung. Am 15. September 2011 wurde die Ehe in Serbien geschieden.
B.
Am 27. Oktober 2012 heirateten A.A._ und B.A._ zum zweiten Mal. Diese reiste am 6. Juni 2014 in die Schweiz ein und ersuchte am 28. August 2014 um Bewilligung des Familiennachzugs zum Ehemann. Mit Verfügung vom 10. Juni 2016 widerrief das Migrationsamt des Kantons Zürich die Niederlassungsbewilligung von A.A._, wies das Gesuch seiner Ehefrau um eine Aufenthaltsbewilligung ab und die beiden aus der Schweiz weg. Die Beschwerden dagegen waren erfolglos.
C.
Vor Bundesgericht beantragen A.A._ und B.A._ mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, in Aufhebung des angefochtenen Urteils des Verwaltungsgerichts des Kantons Zürich vom 11. Juni 2018 vom Widerruf seiner Niederlassungsbewilligung abzusehen und ihr eine Aufenthaltsbewilligung zu erteilen, eventuell die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen, sowie mit subsidiärer Verfassungsbeschwerde, Dispositiv-Ziffer 2 des angefochtenen Urteils aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Sicherheitsdirektion und das Verwaltungsgericht des Kantons Zürich verzichten auf eine Vernehmlassung.
Mit Verfügung vom 31. Juli 2018 erteilte der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde aufschiebende Wirkung.

Erwägungen:
1.
Gegen den Widerruf der Niederlassungsbewilligung steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law> [e contrario]; <ref-ruling> E. 1.2.1 S. 4). In Bezug auf das Begehren der Ehefrau um eine Aufenthaltsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ebenfalls zulässig, da sie - sofern der Widerruf der Niederlassungsbewilligung zu Unrecht erfolgte - Anspruch auf eine solche Bewilligung hat (<ref-law> [SR 142.20; bis zum 1. Januar 2019: AuG (AS 2007 5437)]). Gegen den Entscheid über die als zu kurz gerügte Ausreisefrist ist die subsidiäre Verfassungsbeschwerde zulässig (dazu Urteil 2C_200/2017 vom 14. Juli 2017 E. 1.2.3 und 1.2.4). Da auch die jeweiligen übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde einzutreten.
2.
2.1. Die Niederlassungsbewilligung einer Person ausländischer Staatsangehörigkeit, welche sich seit weniger als fünfzehn Jahren ununterbrochen und ordnungsgemäss in der Schweiz aufhält, kann widerrufen werden, wenn sie oder ihr Vertreter im Bewilligungsverfahren falsche Angaben gemacht oder wesentliche Tatsachen verschwiegen hat (Art. 63 Abs. 1 lit. a und Abs. 2 i.V.m. Art. 62 lit. a AuG). Die falsche Angabe oder das Verschweigen wesentlicher Tatsachen muss in der Absicht erfolgen, gestützt darauf den Aufenthalt oder die Niederlassung bewilligt zu erhalten (<ref-ruling> E. 4.1 S. 9). Liegt ein Widerrufsgrund vor, so ist anschliessend zu prüfen, ob diese Massnahme verhältnismässig erscheint (Art. 96 AuG; <ref-ruling> E. 2.2 S. 147 f.).
2.2. Falsche Angaben im Sinne der genannten Bestimmungen liegen u.a. vor, wenn die Migrationsbehörde über den fehlenden Willen zur Aufnahme einer tatsächlichen ehelichen Lebensgemeinschaft getäuscht wird (Schein-, Umgehungs- oder Ausländerrechtsehe [<ref-ruling> E. 4.2 S. 9 f.]). Ob die Ehe bloss formell bestand, entzieht sich in der Regel dem direkten Beweis und kann nur durch Indizien erstellt werden (<ref-ruling> E. 4.2 S. 9 f.). Solche Indizien können äussere Begebenheiten sein wie eine drohende Wegweisung, das Fehlen einer Wohngemeinschaft, ein erheblicher Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den Ehepartner und dessen Familie oder die Bezahlung einer Entschädigung. Die Indizien können aber auch psychische Vorgänge betreffen (tatsächlicher Wille). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche das Bundesgericht nur auf offensichtliche Unrichtigkeit oder Rechtsverletzungen hin überprüft (<ref-law>; <ref-ruling> E. 2.3 S. 152). In die vorinstanzliche Beweiswürdigung greift es nur ein, wenn diese willkürlich ist (Urteile 2C_752/2016 vom 16. September 2016 E. 3.2; 2C_1141/2015 vom 18. Juli 2016 E. 2.2; zur Willkür in der Beweiswürdigung vgl. <ref-ruling> E. 4.4 S. 444). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften (<ref-ruling> E. 2.3 S. 152).
2.3. Eine Umgehungsehe liegt umgekehrt nicht bereits dann vor, wenn auch ausländerrechtliche Motive die Fortdauer der Lebensgemeinschaft beeinflusst haben. Erforderlich ist, dass der Wille zur Führung der Lebensgemeinschaft im Sinn einer auf Dauer angelegten wirtschaftlichen, körperlichen und spirituellen Verbindung zumindest bei einem der Ehepartner fehlt (<ref-ruling> E. 3b S. 102). Grundsätzlich muss die Migrationsbehörde nachweisen, dass die Ehe nur formell bestand. Dass die Ehe nur zum Schein geführt wird, darf dabei nicht leichthin angenommen werden (<ref-ruling> E. 4.2 S. 10). Die Behörden müssen den Sachverhalt von Amtes wegen möglichst zuverlässig abklären; indessen wird der Untersuchungsgrundsatz durch die Mitwirkungspflicht der Parteien relativiert (vgl. <ref-law>). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vertretbarem Aufwand erhoben werden können (<ref-ruling> E. 5.1 S. 439 m.H; <ref-ruling> E. 8.6.4 S. 496 f.). Anwendbar ist dieser Grundsatz auch dann, wenn aufgrund der gesamten Sachlage sich die Hinweise für einen ausländerrechtlichen Tatbestand so verdichtet haben, dass davon ausgegangen werden kann, dass der strittige Tatbestand vorliegt, wie etwa bei Scheinehen (vgl. Urteil 2C_138/2018 vom 16. Januar 2019 E. 3.2). Insofern besteht quasi eine Tatsachenvermutung. In solchen Konstellationen obliegt es deshalb der Ausländerin bzw. dem Ausländer, den Gegenbeweis zu erbringen. In diesem Fall wird von den Eheleuten erwartet, dass sie von sich aus Umstände vorbringen und belegen, um den echten Ehewillen glaubhaft zu machen.
3.
3.1. Wie die Vorinstanz ausgeführt hat, lagen bereits im Zeitpunkt der Erteilung der Niederlassungsbewilligung Umstände vor, welche auf eine Scheinehe zwischen dem Beschwerdeführer und seiner zweiten Ehefrau hindeuteten: der erhebliche Altersunterschied von 15 Jahren, die einzige Möglichkeit, zu einem gefestigten Anwesenheitsrecht in der Schweiz zu kommen, zwei Wohnungen, wobei der Beschwerdeführer vielfach in der von ihm gemieteten Wohnung übernachtete, die oberhalb seines Restaurant lag, keine gemeinsamen Hobbys, praktisch keine gemeinsame Freizeit und überhaupt keine gemeinsamen Ferien.
3.2. Sind der kantonalen Ausländerbehörde die wesentlichen Umstände, die auf eine Scheinehe hinweisen könnten, im Zeitpunkt der Gesuchseinreichung bekannt und erteilt sie die Niederlassungsbewilligung dennoch, fällt ein späterer Widerruf gestützt auf die bereits bekannten Sachumstände ausser Betracht (vgl. Urteil 2C_801/2013 vom 18. März 2014 E. 3). Im zu beurteilenden Fall haben sich nach der Erteilung der Niederlassungsbewilligung die Sachumstände mit der Scheidung vom 17. September 2011, also rund sechs Monate nach der Erteilung der Niederlassungsbewilligung vom 8. März 2011, und mit der Wiederverheiratung mit der ersten Ehefrau am 27. Oktober 2012 in Mazedonien in ausserordentlichem Mass geändert. Der Beschwerdeführer erfüllt damit - wie die Vorinstanz zu Recht ausgeführt hat - das bekannte Muster einer Schein- bzw. Umgehungsehe, d.h. einer Ehe, der bereits von Anfang an kein Ehewille zugrunde lag. Angesichts dieses Umstandes hat sich die ausländerrechtliche Sachlage so verdichtet, dass davon ausgegangen werden kann, dass der strittige Tatbestand einer Schein- bzw. Umgehungsehe vorliegt, weshalb es dem Ausländer obliegt, den Gegenbeweis zu erbringen (oben E. 2.3). Dies haben die Beschwerdeführer unterlassen und stattdessen fälschlicherweise die Migrationsbehörden dafür verantwortlich erachtet.
3.3. Wie die Vorinstanz zutreffend ausgeführt hat, worauf verwiesen werden kann, erscheint es weder nachvollziehbar noch überzeugend, dass im Verfahren der Niederlassungsbewilligung noch keine eheliche Schwierigkeiten zwischen den Eheleuten bestanden hätten, wenn in Betracht gezogen wird, dass bereits sechs Monate nach dem Verfahren die Scheidung erfolgt ist. Denn einer Scheidung geht in aller Regel ein einige Zeit in Anspruch nehmender Meinungsbildungsprozess voraus. Angesichts dieser Voraussetzung wäre damit das erste Eheproblem mit dem Entschluss zur Scheidung zusammengefallen, was nicht plausibel und realitätsfern ist. Dies bestätigen auch die Aussagen der Eheleute im Scheidungsverfahren, wonach die "Ehegemeinschaft schon einige Zeit nicht mehr existiert", die "Ehebeziehungen ernst und dauerhaft zerrüttet" seien.
Die Vorinstanz hat zudem ausgeführt, dass die Aussagen des Beschwerdeführers und seiner zweiten Ehefrau an der Befragung von 2015 divergieren würden. Die zweite Ehefrau wich zudem in verschiedenen Punkten von ihren Aussagen während des Verfahrens der Niederlassungsbewilligung ab. Sie hat damit das unfertige Bild einer Umgehungsehe während des Verfahrens der Niederlassungsbewilligung nunmehr vervollständigt. Der Beschwerdeführer vertritt indessen die Auffassung, dass nicht er, sondern die zweite Ehefrau die Scheidung gewollt habe und deren Aussagen von 2015 nicht der Wahrheit entsprechen, da sie der deutschen Sprache nicht derart mächtig sei, dass sie den Inhalt verstanden habe. Die zweite Ehefrau ist mittlerweile Schweizerin geworden, wie der Beschwerdeführer festhält. Nach <ref-law> (SR 141.0) ist eine Einbürgerung nur möglich, wenn die Bewerberin erfolgreich integriert ist. Nach <ref-law> gehört die Fähigkeit dazu, sich im Alltag in Wort und Schrift in einer Landessprache zu verständigen. Da die zweite Ehefrau sich im Kanton Zürich eingebürgert hat, kann ohne Weiteres davon ausgegangen werden, dass sie die in Deutsch gestellten Fragen der Befragung verstanden hat, was sie im Übrigen im Verlauf des Widerrufsverfahrens selber bestätigt hat. Ob die zweite Ehefrau die Scheidung veranlasst hat, ist hier nicht entscheidend. Entscheidend ist, dass der Ehewille des Beschwerdeführers von Anfang nicht bestanden hatte.
3.4. Ebensowenig ist glaubhaft, dass es in der kurzen Zeit von einem Jahr seit der Scheidung von seiner zweiten Ehefrau zur Wiederannäherung samt Wiederverheiratung zwischen den früheren Ehegatten gekommen ist, wie die Vorinstanz zutreffend ausgeführt hat. Der Beschwerdeführer führt dabei an, dass die Vorinstanz verschiedene Abklärungen im Aufenthaltsland der Beschwerdeführerin hätte einholen müssen. Wären solche erfolgt, hätte sich ergeben, dass keine Scheinehe und keine Parallelbeziehung bestanden hätte. Bei seiner Argumentation vergisst der Beschwerdeführer, dass aufgrund des bekannten Musters einer Schein- bzw. Umgehungsehees an ihm gelegen wäre, den Gegenbeweis anzutreten. Im vorliegenden Fall geht es auch nicht darum, dass die Behörde eine eigentliche Parallelbeziehung nachzuweisen hätte. Insofern erübrigten sich daher die vor Vorinstanz vorgebrachten Begehren, wonach dazu Zeugen anzuhören seien.
3.5. Zusammenfassend ergibt sich, dass - wie die Vorinstanz zutreffend dargelegt hat - der Beschwerdeführer mit seiner zweiten Ehefrau eine Umgehungsehe eingegangen ist und im Bewilligungsverfahren falsche Angaben gemacht bzw. wesentliche Tatsachen verschwiegen und damit den Widerrufsgrund nach Art. 63 Abs. 1 lit. a i.V.m. Art. 62 Abs. 1 lit. a AuG erfüllt hat.
4.
Im Folgenden ist zu prüfen, ob der Widerruf verhältnismässig erscheint (<ref-law>; <ref-ruling> E. 2.2 S. 147 f.).
4.1. Das öffentliche Interessen ist gewichtig, hat der Beschwerdeführer doch durch Täuschung versucht, eine Niederlassungsbewilligung zu erwerben. Kommt hinzu, dass der Beschwerdeführer auch strafrechtlich in Erscheinung getreten ist (Inverkehrbringen wertverminderter, verdorbener Lebensmittel [zweimal], Verkehrsregelverletzung), was das Gewicht des öffentlichen Interessens aufgrund der Scheinehe leicht erhöht.
4.2. Der Beschwerdeführer ist mit 34 Jahren in die Schweiz eingereist und hält sich seit etwas mehr als zwölf Jahren hier auf. Allerdings ist das Gewicht der Anwesenheitsdauer gering, da das Aufenthaltsrecht auf einer Täuschung beruht. Der Beschwerdeführer macht diesbezüglich geltend, dass die Dauer der Anwesenheit - wie Art. 63 Abs. 2 AuG nahelege - zu berücksichtigen sei, da hier kein Fall von Art. 63 Abs. 1 lit. b und Art. 62 Abs. 1 lit. b AuG vorliege. Art. 63 Abs. 2 AuG bezieht sich auf die Frage, ob ein Widerrufsgrund vorliegt. Hier steht indes die Frage im Vordergrund, welches Gewicht der Dauer der Anwesenheit zukommt. Dabei spielt eine wesentliche Rolle, ob die Anwesenheitsberechtigung durch Täuschung der Behörden erlangt worden ist. Die wirtschaftliche, soziale und sprachliche Integration ist normal. Dadurch, dass der Beschwerdeführer sich am wirtschaftlichen Prozess beteiligt und die deutsche Sprache spricht, handelt es sich - entgegen den Ausführungen des Beschwerdeführers - nicht um eine besonders hervorzuhebende Integration. Der Beschwerdeführer ist in Serbien und Mazedonien während 34 Jahren sozialisiert worden, dort zur Schule gegangen und hat dort die berufliche Ausbildung abgeschlossen. Er verbrachte in diesen beiden Ländern seine Ferien, besuchte seine Kinder und die Beschwerdeführerin. In der Schweiz hat er keine Kinder, für welche er zu sorgen hat. Auch die medizinische Versorgung seiner Krankheit ist in Mazedonien sichergestellt, wie er vor den Vorinstanzen einräumte. Insgesamt ist das Gewicht der privaten Interessen gering.
4.3. Wie die Vorinstanz zutreffend festgehalten hat, überwiegt das öffentliche Interesse an der Beendigung des Aufenthalts des Beschwerdeführers dessen private Interessen an einem Verbleib in der Schweiz. Zwar dürfte nach zwölf Jahren Wohnsitz in der Schweiz ein Umzug nach Serbien oder Mazedonien nicht leicht fallen. Allerdings kehrt er zusammen mit seiner Ehefrau dorthin zurück, kennt die dortigen Gewohnheiten wegen seiner Sozialisierung (Sprache, Sitte etc.) und den Besuchen. Zudem hat er in beiden Staaten Grundeigentum.
5.
Die Beschwerdeführerin macht einen abgeleiteten Anspruch nach Art. 43 Abs. 1 AuG geltend. Besteht aber kein originärer Anspruch des Beschwerdeführers, ist ein abgeleiteter Anspruch der Beschwerdeführerin nicht möglich. Art. 8 EMRK in seinem Aspekt des Familienlebens scheitert mangels eines gefestigten Rechtsanspruchs des Beschwerdeführers, in seinem Aspekt des Privatlebens mangels Integration der Beschwerdeführerin (zum Ganzen <ref-ruling>).
6.
6.1. Nach Dispositiv-Ziffer 2 i.V.m. Erwägung 7.2 des vorinstanzlichen Entscheids haben sich der Beschwerdeführer und die Beschwerdeführerin binnen eines Monats ab Zustellung eines den Wegweisungspunkt nicht ändernden bundesgerichtlichen Endentscheids aus dem Land zu entfernen. Der Beschwerdeführer macht diesbezüglich geltend, dass die Frist von einem Monat für die Auflösung der beiden Restaurants und den Verkauf der Liegenschaft angesichts seiner angeschlagenen Gesundheit zu kurz bemessen, also willkürlich sei.
6.2. 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. Das Bundesgericht hebt einen Entscheid nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist (vgl. <ref-ruling> E. 3.4 S. 53).
6.3. Nach <ref-law> ist mit der Wegweisungsverfügung eine angemessene Ausreisefrist zwischen sieben und dreissig Tagen anzusetzen. Eine längere Ausreisefrist ist anzusetzen oder die Ausreisefrist ist zu verlängern, wenn besondere Umstände wie die familiäre Situation, gesundheitliche Probleme oder eine lange Aufenthaltsdauer dies erfordern. Die Kriterien für die Verlängerungen der Ausreisefrist sind lediglich Beispiele, wie das Wort "wie" insinuiert. Die Erstreckung der Ausreisefrist über den gesetzlichen Regelrahmen von sieben bis dreissig Tage darf indes nicht dazu dienen, dem weggewiesenen Ausländer faktisch eine Bewilligungsverlängerung zu gewähren. Bei der Festsetzung der Frist ist auch zu berücksichtigen, dass der Ausländer die Möglichkeit bereits früh in Betracht zu ziehen hat, wobei von ihm allerdings vor Eintritt der Rechtskraft nicht erwartet werden muss, dass er auch schon nicht rückgängig zu machende organisatorische Massnahmen trifft. Hingegen ist ihm zuzumuten, dass er ab dem Zeitpunkt der Kenntnisnahme von der Rechtskraft des Wegweisungsentscheids die für die Ausreise notwendigen Vorkehrungen trifft und nicht tatenlos eine Fristansetzung abwarten darf (Urteil 2C_634/2018 vom 5. Februar 2019 E. 8.3.1 mit Hinweisen).
6.4. Im Fall des Beschwerdeführers stehen neben seinen gesundheitlichen Problemen die Auflösung der beiden Restaurants mit 30 Angestellten sowie der Verkauf der beiden Liegenschaften im Vordergrund. Eine geordnete Beendigung der Arbeitsverträge mit den Angestellten und der Verkauf der beiden Liegenschaften bedarf mehr Zeit als 30 Tage: So sind Kündigungsfristen für das Personal einzuhalten und geeignete Käufer für die Liegenschaften zu finden, andernfalls dem Beschwerdeführer ein beträchtlicher finanzieller Schaden erwachsen würde. Zieht man sodann in Betracht, dass der Beschwerdeführer gesundheitlich angeschlagen ist, er also mehr Zeit für seine Arbeiten einsetzen muss, so läuft der Entscheid der Vorinstanz, wonach der Beschwerdeführer innert 30 Tagen auszureisen habe, in stossender Weise dem Gerechtigkeitsgedanken zuwider. Der Entscheid ist offensichtlich unhaltbar und die subsidiäre Verfassungsbeschwerde gutzuheissen. Aufgrund der dargestellten Situation dürfte eine Frist von ungefähr drei Monaten als nicht willkürlich erscheinen. Antragsgemäss hat aber die Vorinstanz aufgrund der Berücksichtigung aller Aspekte die genaue Dauer festzulegen. Dass der Beschwerdeführer die beiden Restaurants nicht bereits früher aufgelöst und die Liegenschaften verkauft hat, ist nachvollziehbar, hängt doch davon sein Lebensunterhalt ab.
7.
Dementsprechend ist die subsidiäre Verfassungsbeschwerde gutzuheissen, Ziffer 2 des vorinstanzlichen Dispositivs aufzuheben und die Sache im Sinne von Erwägung 6.4 zum neuen Entscheid an die Vorinstanz zurückzuweisen. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist demgegenüber abzuweisen. Bei diesem Verfahrensausgang mit teilweisem Obsiegen trägt der Beschwerdeführer reduzierte Gerichtskosten (<ref-law>). Er hat Anspruch auf teilweisen Ersatz seiner Parteikosten durch den Kanton Zürich (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2.
Die subsidiäre Verfassungsbeschwerde wird gutgeheissen. Dispositiv-Ziff. 2 des angefochtenen Entscheids wird aufgehoben und die Sache zur Ansetzung einer neuen Ausreisefrist im Sinne von Erwägung 6.4 an die Vorinstanz zurückgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer und der Beschwerdeführerin in solidarischer Haftung auferlegt.
4.
Der Kanton Zürich schuldet dem Beschwerdeführer und der Beschwerdeführerin eine Parteientschädigung von Fr. 1'250.--.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 4. April 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Errass