Beaverland terdiri atas $N$ kota, bernomor $1$ hingga $N$. Ada $M$ jalan yang menghubungkan kota-kota, bernomor $1$ hingga $M$. Jalan $i$ ($1\le i\le M$) menghubungkan kota $A_i$ dan kota $B_i$ dalam kedua arah, dan panjangnya adalah $C_i$. Setiap kota dapat dicapai dari kota lain dengan melewati sejumlah jalan.

Bitaro adalah seekor berang-berang yang tinggal di kota $1$. Ia bersekolah di kota $N$. Biasanya ia selalu menempuh rute yang sama ke sekolah. Rutenya memenuhi ketentuan berikut.

• Misalkan $L$ adalah jarak minimum dari kota $1$ ke kota $N$.
• Rute Bitaro ke sekolah menghubungkan kota $1$ dan kota $N$, dan panjangnya adalah $L$.

Karena cuaca hari ini cerah, Bitaro memutuskan pulang dengan mengambil jalan memutar. Artinya, ia akan menempuh rute dari kota $N$ ke kota $1$ yang panjangnya lebih dari $L$. Bitaro mudah bosan, sehingga ia tidak ingin mengunjungi kota yang sama lebih dari sekali. Oleh karena itu, ketika mengambil jalan memutar untuk pulang, ia tidak boleh mengunjungi kota yang sama lebih dari sekali dan tidak boleh berbalik arah di tengah perjalanan.

Diberikan informasi kota-kota dan jalan-jalan di Beaverland, tulislah program yang menentukan apakah ada jalan memutar dari sekolah ke rumah Bitaro.

Masukan

Baca data berikut dari masukan standar. Semua nilai yang diberikan adalah bilangan bulat.

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

Keluaran

Tuliskan satu baris ke keluaran standar. Keluarkan 1 jika ada rute pulang ke rumah Bitaro yang panjangnya lebih dari $L$ tanpa mengunjungi kota yang sama lebih dari sekali. Jika tidak, keluarkan 0.

Batasan

• $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$).
• Setiap kota dapat dicapai dari kota lain dengan melewati sejumlah jalan.

Subsoal

1. (7 poin) $M\le40$.
2. (15 poin) $N\le18$.
3. (23 poin) $M-N\le13$.
4. (35 poin) Untuk setiap tiga kota berbeda $a,b,c$, ada rute dari kota $a$ ke kota $c$ tanpa melalui kota $b$.
5. (20 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

0

Catatan

Dalam contoh ini, jarak minimum dari kota 1 (rumah Bitaro) ke kota 4 (sekolah) adalah 5.

Ada dua rute pulang ke rumah Bitaro tanpa mengunjungi kota yang sama lebih dari sekali.

• Rute sepanjang 5 yang melewati jalan $3\to1$ secara berurutan dan mengunjungi kota $4\to2\to1$ secara berurutan.
• Rute sepanjang 5 yang melewati jalan $4\to2$ secara berurutan dan mengunjungi kota $4\to3\to1$ secara berurutan.

Karena tidak ada rute pulang ke rumah Bitaro yang panjangnya lebih dari 5 tanpa mengunjungi kota yang sama lebih dari sekali, keluarkan 0.

Contoh masukan ini memenuhi batasan semua subsoal.

Masukan 2

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

Keluaran 2

1

Catatan

Dalam contoh ini, jarak minimum dari kota 1 (rumah Bitaro) ke kota 4 (sekolah) adalah 5.

Ada dua rute pulang ke rumah Bitaro tanpa mengunjungi kota yang sama lebih dari sekali.

• Rute sepanjang 5 yang melewati jalan $3\to1$ secara berurutan dan mengunjungi kota $4\to2\to1$ secara berurutan.
• Rute sepanjang 6 yang melewati jalan $4\to2$ secara berurutan dan mengunjungi kota $4\to3\to1$ secara berurutan.

Karena ada rute pulang ke rumah Bitaro yang panjangnya lebih dari 5 tanpa mengunjungi kota yang sama lebih dari sekali, keluarkan 1.

Contoh masukan ini memenuhi batasan semua subsoal.

Masukan 3

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

Keluaran 3

0

Catatan

Contoh masukan ini memenuhi batasan subsoal 1, 2, 3, 5.

Masukan 4

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

Keluaran 4

1

Catatan

Contoh masukan ini memenuhi batasan semua subsoal.

Masukan 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

Keluaran 5

0

Catatan

Contoh masukan ini memenuhi batasan subsoal 1, 2, 3, 5.