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 вирішив повернутися додому обхідним шляхом. Тобто він пройде з міста $N$ до міста $1$ маршрутом, довшим за $L$. Оскільки Bitaro легко нудьгує, він не хоче відвідувати те саме місто більше одного разу. Тому, коли він повертається додому обхідним шляхом, не дозволяється відвідувати те саме місто більше одного разу чи повертати назад посеред дороги.

За інформацією про міста й дороги Beaverland напишіть програму, яка визначає, чи існує обхідний шлях зі школи до дому Bitaro.

Вхідні дані

Прочитайте такі дані зі стандартного вводу. Усі задані значення — цілі числа.

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

Вихідні дані

Виведіть один рядок у стандартний вивід. Виведіть $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.