تتكوّن Beaverland من $N$ مدن، مرقّمة من $1$ إلى $N$. توجد $M$ طرق تصل بين المدن، مرقّمة من $1$ إلى $M$. يصل الطريق رقم $i$ ($1 \le i \le M$) بين المدينتين $A_i$ و$B_i$ في الاتجاهين، وطوله $C_i$. يمكن الانتقال من أي مدينة إلى أي مدينة أخرى بالمرور عبر عدد من الطرق.

Bitaro قندس يسكن في المدينة $1$. يذهب إلى مدرسة في المدينة $N$. وعادةً ما يسلك المسار نفسه إلى المدرسة. يحقق مساره إلى المدرسة الشروط التالية.

• ليكن $L$ أقصر مسافة من المدينة $1$ إلى المدينة $N$.
• يصل مسار Bitaro إلى المدرسة بين المدينة $1$ والمدينة $N$، وطوله $L$.

بما أن الطقس جميل اليوم، قرر Bitaro العودة إلى منزله عبر طريق ملتف. أي إنه سيسلك مسارًا طوله أكبر من $L$ من المدينة $N$ إلى المدينة $1$. ولأن Bitaro يملّ بسهولة، فإنه لا يريد زيارة المدينة نفسها أكثر من مرة. لذلك، عندما يسلك طريقًا ملتفًا إلى منزله، لا يُسمح له بزيارة المدينة نفسها أكثر من مرة، ولا يُسمح له بالرجوع أدراجه أثناء الطريق.

بمعرفة معلومات المدن والطرق في Beaverland، اكتب برنامجًا يحدد ما إذا كان هناك طريق ملتف من المدرسة إلى منزل Bitaro.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي. جميع القيم المعطاة أعداد صحيحة.

$$ \begin{array}{l} N\ M\\ A_1\ B_1\ C_1\\ A_2\ B_2\ C_2\\ \vdots\\ A_M\ B_M\ C_M \end{array} $$

الإخراج

اطبع سطرًا واحدًا إلى الإخراج القياسي. اطبع 1 إذا وُجد مسار إلى منزل Bitaro طوله أكبر من $L$ ولا يزور المدينة نفسها أكثر من مرة. وإلا فاطبع 0.

القيود

• $2 \le N \le 100\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$).
• $1 \le C_i \le 1\,000\,000\,000\ (=10^9)$ ($1 \le i \le M$).
• يمكن الانتقال من أي مدينة إلى أي مدينة أخرى بالمرور عبر عدد من الطرق.

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

1. (7 نقاط) $M \le 40$.
2. (15 نقطة) $N \le 18$.
3. (23 نقطة) $M-N \le 13$.
4. (35 نقطة) لأي ثلاث مدن مختلفة $a,b,c$، يوجد مسار من المدينة $a$ إلى المدينة $c$ لا يمر بالمدينة $b$.
5. (20 نقطة) لا توجد قيود إضافية.

أمثلة

الإدخال 1

4 4
1 2 1
1 3 2
2 4 4
3 4 3

الإخراج 1

0

ملاحظة

في مثال الإدخال هذا، أقصر مسافة من المدينة $1$ (منزل Bitaro) إلى المدينة $4$ (المدرسة) هي $5$.

يوجد مساران إلى منزل Bitaro لا يزوران المدينة نفسها أكثر من مرة.

• مسار طوله $5$ يمر بالطريقين $3\to1$ بهذا الترتيب، ويزور المدن $4\to2\to1$ بهذا الترتيب.
• مسار طوله $5$ يمر بالطريقين $4\to2$ بهذا الترتيب، ويزور المدن $4\to3\to1$ بهذا الترتيب.

بما أنه لا يوجد مسار إلى منزل Bitaro طوله أكبر من $5$ ولا يزور المدينة نفسها أكثر من مرة، فاطبع 0.

يحقق مثال الإدخال هذا قيود جميع المهام الفرعية.

الإدخال 2

4 4
1 2 1
1 3 3
2 4 4
3 4 3

الإخراج 2

1

ملاحظة

في مثال الإدخال هذا، أقصر مسافة من المدينة $1$ (منزل Bitaro) إلى المدينة $4$ (المدرسة) هي $5$.

يوجد مساران إلى منزل Bitaro لا يزوران المدينة نفسها أكثر من مرة.

• مسار طوله $5$ يمر بالطريقين $3\to1$ بهذا الترتيب، ويزور المدن $4\to2\to1$ بهذا الترتيب.
• مسار طوله $6$ يمر بالطريقين $4\to2$ بهذا الترتيب، ويزور المدن $4\to3\to1$ بهذا الترتيب.

بما أنه يوجد مسار إلى منزل Bitaro طوله أكبر من $5$ ولا يزور المدينة نفسها أكثر من مرة، فاطبع 1.

يحقق مثال الإدخال هذا قيود جميع المهام الفرعية.

الإدخال 3

3 4
1 2 1
1 2 2
1 3 3
1 3 3

الإخراج 3

0

ملاحظة

يحقق مثال الإدخال هذا قيود المهام الفرعية 1 و2 و3 و5.

الإدخال 4

4 5
1 2 1
1 3 2
2 4 4
3 4 3
2 3 1

الإخراج 4

1

ملاحظة

يحقق مثال الإدخال هذا قيود جميع المهام الفرعية.

الإدخال 5

12 17
2 4 656247308
4 6 106088453
1 5 754343261
9 12 497827261
3 8 759830309
3 4 61084725
1 6 324702188
3 6 415317430
7 12 846175092
5 8 278621369
1 10 891247646
10 12 755236904
6 8 511967203
5 6 597197970
1 7 800309458
7 9 348347831
10 11 134217757

الإخراج 5

0

ملاحظة

يحقق مثال الإدخال هذا قيود المهام الفرعية 1 و2 و3 و5.