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$ 沿一條長度大過 $L$ 嘅路線去城市 $1$。Bitaro 好容易覺得悶，唔想到訪同一座城市超過一次。所以，佢兜路返屋企嗰陣，唔可以到訪同一座城市超過一次，亦唔可以中途掉頭。
畀定 Beaverland 嘅城市同道路資料，請寫一個程式，判斷有冇一條由學校兜路返 Bitaro 屋企嘅路線。
輸入格式
由標準輸入讀入以下資料。所有輸入值都係整數。
N M A_1 B_1 C_1 A_2 B_2 C_2 ... A_M B_M C_M
輸出格式
向標準輸出寫出一行。如果存在一條返 Bitaro 屋企嘅路線，長度大過 $L$，而且唔會到訪同一座城市超過一次，就輸出 1。否則，輸出 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$）。
- 由任何一座城市出發，都可以經若干條道路去到任何另一座城市。
子任務
- （7 分）$M \le 40$。
- （15 分）$N \le 18$。
- （23 分）$M-N \le 13$。
- （35 分）對任何互不相同嘅城市 $a,b,c$，都存在一條由城市 $a$ 去城市 $c$ 而唔經城市 $b$ 嘅路線。
- （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$ 嘅限制。