تتكون قرية KOI من $N$ مبنى و$M$ طريقًا.

تُرقم المباني من 1 إلى $N$، ولكل مبنى نوافذ أو لا نوافذ له. لكل $i$ يحقق $1\le i\le N$، تكون $c_i=1$ إذا كان للمبنى $i$ نوافذ، و$c_i=0$ خلاف ذلك. ليس للمبنيين 1 و$N$ نوافذ، لذا $c_1=c_N=0$.

تُرقم الطرق من 1 إلى $M$. كل طريق أحادي الاتجاه ويصل مبنى بداية واحدًا بالضبط بمبنى وصول واحد. لكل $j$ يحقق $1\le j\le M$، يبدأ الطريق $j$ من المبنى $x_j$ وينتهي عند المبنى $y_j$، ويستغرق عبوره $t_j$ ثانية بالضبط. لا يمكن السير في الاتجاه المعاكس، أي من $y_j$ إلى $x_j$.

يريد 한국 و정올 في قرية KOI لعب النسخة المعدلة التالية من لعبة «أزهرت الكركديه».

عند البداية، يكون 정올 في المبنى 1. هدفه الوصول إلى المبنى $N$ بأسرع ما يمكن دون أن يراه 한국 ولو مرة واحدة. أما 한국 فيريد اكتشاف 정올 قبل وصوله إلى المبنى $N$.

عندما تكون عيناه مفتوحتين، يستطيع 한국 رؤية قرية KOI كلها، لكنه لا يستطيع رؤية داخل المباني التي لا نوافذ لها. أي إنه لا يرى إلا الطرق وداخل المباني ذات النوافذ.

منذ بداية اللعبة عند الزمن 0، يكرر 한국 الأفعال التالية دوريًا.

• يغلق عينيه أولًا لمدة $a$ ثانية بالضبط، ثم يفتحهما مباشرة ويراقب القرية لمدة $b$ ثانية بالضبط.
• يغلق عينيه مجددًا لمدة $a$ ثانية، ثم يفتحهما مباشرة ويراقب القرية لمدة $b$ ثانية بالضبط.
• يكرر هذه العملية دون توقف.

التعريف الرياضي الدقيق لهذه العملية كما يلي.

• نعرّف الزمن الحالي بأنه الوقت المنقضي منذ بدء اللعبة، بالثواني.
• إذا كان الزمن الحالي $t$، فاكتب $t=k(a+b)+l$، حيث $k$ عدد صحيح غير سالب و$l$ عدد حقيقي يحقق $0\le l<a+b$.
• إذا كان $0\le l\le a$، تكون عينا 한국 مغلقتين، وإذا كان $a<l<a+b$، تكونان مفتوحتين.
• أي إنه لكل عدد صحيح غير سالب $k$، تكون عيناه مغلقتين خلال الفترة المغلقة $[k(a+b),k(a+b)+a]$، ومفتوحتين خلال الفترة المفتوحة $(k(a+b)+a,(k+1)(a+b))$.

يمكن لـ 정올 بدء التحرك متى شاء ابتداءً من الزمن 0، والانتظار داخل أي مبنى ما شاء من الوقت سواء كانت له نوافذ أم لا. لا يستغرق الخروج من مبنى إلى طريق أو الدخول من طريق إلى مبنى أي وقت. إذا بدأ عبور طريق، فيجب أن يتحرك لمدة عبوره بالضبط، ولا يمكنه التوقف أو الانتظار على الطريق أثناء ذلك. وعند انتهاء الحركة يصل إلى المبنى في نهاية الطريق.

يكتشف 한국 وجود 정올 وفق القواعد التالية.

• إذا كانت عينا 한국 مفتوحتين وكان 정올 على طريق أو داخل مبنى ذي نوافذ، يُكتشف فورًا وتنتهي اللعبة مباشرة. لذلك يجب أن يكون 정올 داخل مبنى بلا نوافذ طوال وقت فتح 한국 عينيه.
• حين تكون عينا 한국 مغلقتين، لا يُكتشف 정올 إطلاقًا أينما كان.
• لاحظ أن 정올 لا يُكتشف إذا دخل مبنى بلا نوافذ في اللحظة نفسها التي يبدأ فيها 한국 فتح عينيه، أو دخل طريقًا وبدأ التحرك في اللحظة نفسها التي يبدأ فيها 한국 إغلاقهما.

اكتب برنامجًا يحدد، في هذه الظروف، ما إذا كان 정올 يستطيع الوصول بأمان إلى المبنى $N$ دون أن يُكتشف ولو مرة واحدة، وإن أمكن، يحسب أبكر زمن وصول ممكن بالثواني.

القيود

• جميع الأعداد المعطاة صحيحة.
• $3\le N\le2\,000$.
• $3\le M\le4\,000$.
• لكل $j$ يحقق $1\le j\le M$، لدينا $1\le x_j,y_j\le N$ و$x_j\ne y_j$ و$1\le t_j\le100\,000$.
• لكل $j,k$ يحققان $1\le j<k\le M$، لدينا $(x_j,y_j)\ne(x_k,y_k)$. أي لا يوجد طريقان لهما مبنى البداية نفسه ومبنى الوصول نفسه معًا.
• لكل $i$ يحقق $2\le i\le N-1$، لدينا $c_i\in\{0,1\}$.
• $c_1=c_N=0$، أي ليس للمبنيين 1 و$N$ نوافذ.
• $1\le a,b\le10^9$.

المهام الفرعية

1. (12 نقطة) $N\le5$ و$M\le10$.
2. (19 نقطة) لكل $i$ يحقق $2\le i\le N-1$، لدينا $c_i=1$.
3. (31 نقطة) لكل $j$ يحقق $1\le j\le M$، لدينا $t_j=1$.
4. (27 نقطة) $M=N-1$. وأيضًا، لكل $j$ يحقق $1\le j\le N-1$، لدينا $x_j=j$ و$y_j=j+1$.
5. (61 نقطة) لا توجد قيود إضافية.

الإدخال

يحتوي السطر الأول على عددين صحيحين $N$ و$M$ تفصل بينهما مسافة.

تصف الأسطر الـ $M$ التالية الطرق. يحتوي السطر $j$ منها ($1\le j\le M$) على ثلاثة أعداد صحيحة $x_j,y_j,t_j$ مفصولة بمسافات.

يحتوي السطر التالي على $N$ عددًا صحيحًا هي $c_1,c_2,\ldots,c_N$ مفصولة بمسافات.

يحتوي السطر التالي على عددين صحيحين $a,b$ تفصل بينهما مسافة.

الإخراج

إذا لم يستطع 정올 الوصول إلى المبنى $N$ مهما كانت حركته، فاطبع -1.

خلاف ذلك، اطبع أقل وقت بالثواني يحتاجه 정올 للوصول إلى المبنى $N$. يمكن إثبات أن هذه القيمة عدد صحيح دائمًا.

أمثلة

الإدخال 1

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 0 0 0
3 8

الإخراج 1

14

ملاحظة

مع مرور الوقت، يمكن لـ 정올 و한국 التصرف كما يلي.

• من 0 إلى 3 ثوانٍ: عينا 한국 مغلقتان. يدخل 정올 الطريق 1 (المبنى 1 → المبنى 2) عند الزمن 0، ويصل إلى المبنى 2 عند الزمن 3.
• من 3 إلى 11 ثانية: يفتح 한국 عينيه عند الزمن 3. يبقى 정올 في المبنى 2 حتى الزمن 11.
• من 11 إلى 14 ثانية: يغلق 한국 عينيه عند الزمن 11. يدخل 정올 عندها الطريق 3 (المبنى 2 → المبنى 4)، ويصل إلى المبنى 4 عند الزمن 14.

لا توجد طريقة لوصول 정올 إلى المبنى 4 قبل الزمن 14، لذا يجب طباعة 14.

الإدخال 2

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 1 1 0
3 8

الإخراج 2

-1

ملاحظة

لجميع المباني عدا 1 و4 نوافذ، لذا يجب أن يصل 정올 إلى المبنى 4 قبل أن يفتح 한국 عينيه، أي خلال $a=3$ ثوانٍ. لكن الوصول إليه خلال 3 ثوانٍ مستحيل، لذا يجب طباعة -1.