Beaverland besteht aus $N$ Städten, die von $1$ bis $N$ nummeriert sind. Es gibt $M$ Straßen zwischen den Städten, die von $1$ bis $M$ nummeriert sind. Straße $i$ ($1\le i\le M$) verbindet Stadt $A_i$ und Stadt $B_i$ in beiden Richtungen und hat die Länge $C_i$. Jede Stadt ist von jeder anderen Stadt über eine Folge von Straßen erreichbar.

Bitaro ist ein Biber, der in Stadt $1$ wohnt. Er besucht eine Schule in Stadt $N$. Normalerweise nimmt er immer denselben Schulweg. Sein Schulweg erfüllt die folgenden Bedingungen.

• Sei $L$ die kürzeste Entfernung von Stadt $1$ nach Stadt $N$.
• Bitaros Schulweg verbindet Stadt $1$ mit Stadt $N$ und hat die Länge $L$.

Da heute schönes Wetter ist, hat Bitaro beschlossen, auf einem Umweg nach Hause zu gehen. Er wird also einen Weg von Stadt $N$ nach Stadt $1$ nehmen, der länger als $L$ ist. Da sich Bitaro schnell langweilt, möchte er keine Stadt mehr als einmal besuchen. Auf seinem Umweg nach Hause darf er daher keine Stadt mehr als einmal besuchen und unterwegs nicht umkehren.

Schreibe ein Programm, das anhand der Informationen über die Städte und Straßen in Beaverland bestimmt, ob es einen Umweg von der Schule zu Bitaros Zuhause gibt.

Eingabe

Lies die folgenden Daten von der Standardeingabe. Alle angegebenen Werte sind ganze Zahlen.

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

Ausgabe

Gib eine Zeile auf der Standardausgabe aus. Gib $1$ aus, falls es einen Weg zu Bitaros Zuhause gibt, der länger als $L$ ist und keine Stadt mehr als einmal besucht. Andernfalls gib $0$ aus.

Beschränkungen

• $2\le N\le100\,000$.
• $1\le M\le200\,000$.
• $1\le A_i<B_i\le N$ ($1\le i\le M$).
• $1\le C_i\le1\,000\,000\,000\ (=10^9)$ ($1\le i\le M$).
• Jede Stadt ist von jeder anderen Stadt über eine Folge von Straßen erreichbar.

Teilaufgaben

1. (7 Punkte) $M\le40$.
2. (15 Punkte) $N\le18$.
3. (23 Punkte) $M-N\le13$.
4. (35 Punkte) Für je drei verschiedene Städte $a,b,c$ gibt es einen Weg von Stadt $a$ nach Stadt $c$, der nicht durch Stadt $b$ führt.
5. (20 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

0

Hinweis

In diesem Beispiel beträgt die kürzeste Entfernung von Stadt $1$ (Bitaros Zuhause) nach Stadt $4$ (Schule) $5$.

Es gibt zwei Wege zu Bitaros Zuhause, die keine Stadt mehr als einmal besuchen.

• Einen Weg der Länge $5$, der die Straßen $3\to1$ in dieser Reihenfolge durchläuft und die Städte $4\to2\to1$ in dieser Reihenfolge besucht.
• Einen Weg der Länge $5$, der die Straßen $4\to2$ in dieser Reihenfolge durchläuft und die Städte $4\to3\to1$ in dieser Reihenfolge besucht.

Da es keinen Weg zu Bitaros Zuhause gibt, der länger als $5$ ist und keine Stadt mehr als einmal besucht, gib $0$ aus.

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.

Eingabe 2

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

Ausgabe 2

1

Hinweis

In diesem Beispiel beträgt die kürzeste Entfernung von Stadt $1$ (Bitaros Zuhause) nach Stadt $4$ (Schule) $5$.

Es gibt zwei Wege zu Bitaros Zuhause, die keine Stadt mehr als einmal besuchen.

• Einen Weg der Länge $5$, der die Straßen $3\to1$ in dieser Reihenfolge durchläuft und die Städte $4\to2\to1$ in dieser Reihenfolge besucht.
• Einen Weg der Länge $6$, der die Straßen $4\to2$ in dieser Reihenfolge durchläuft und die Städte $4\to3\to1$ in dieser Reihenfolge besucht.

Da es einen Weg zu Bitaros Zuhause gibt, der länger als $5$ ist und keine Stadt mehr als einmal besucht, gib $1$ aus.

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.

Eingabe 3

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

Ausgabe 3

0

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 2, 3 und 5.

Eingabe 4

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

Ausgabe 4

1

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.

Eingabe 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

Ausgabe 5

0

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 2, 3 und 5.