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.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי. כל הערכים הנתונים הם מספרים שלמים.

$N\ M$

$A_1\ B_1\ C_1$

$A_2\ B_2\ C_2$

$\vdots$

$A_M\ B_M\ C_M$

פלט

כתבו שורה אחת לפלט הסטנדרטי. הדפיסו 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 \to 1$ בסדר זה, ומבקר בערים $4 \to 2 \to 1$ בסדר זה.
• מסלול באורך $5$ העובר בכבישים $4 \to 2$ בסדר זה, ומבקר בערים $4 \to 3 \to 1$ בסדר זה.

מכיוון שלא קיים מסלול לביתו של 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 \to 1$ בסדר זה, ומבקר בערים $4 \to 2 \to 1$ בסדר זה.
• מסלול באורך $6$ העובר בכבישים $4 \to 2$ בסדר זה, ומבקר בערים $4 \to 3 \to 1$ בסדר זה.

מכיוון שקיים מסלול לביתו של 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.