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{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 \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