Farmer John は Farmer Dan に荷物を届けるため旅の準備をしています。平和を保つため、途中で会う牛にそれぞれおいしいおやつを渡します。倹約家なので、会う牛の数をなるべく減らしたいと考えています。

地図には $N$ 個の牛舎（$1 \le N \le 50,000$）と、それらを結ぶ $M$ 本の双方向の道（$1 \le M \le 50,000$）があります。道には $C_{i}$ 頭（$0 \le C_{i} \le 1,000$）の牛が歩いています。各道は異なる牛舎 $A_{i}$ と $B_{i}$（$1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$）を結び、同じ 2 個を複数の道が直接結んでも構いません。FJ は牛舎 1、Farmer Dan は牛舎 $N$ にいます。

次の地図を考えます。

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3

最良の経路は 1 → 2 → 4 → 5 → 6 で、1 + 0 + 3 + 1 = 5 個のおやつが必要です。

会った異なる牛それぞれにちょうど 1 個のおやつを渡すとき、持っていく最小個数を求めてください。旅の長さは気にしません。

入力

• 1 行目：空白区切りの整数 $N$ と $M$。
• $2..M+1$ 行目：空白区切りの整数 $A_{i}$、$B_{i}$、$C_{i}$。

出力

• 1 行目：必要なおやつの最小個数。

入出力例

入力 1

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

出力 1

5

問題作成者：Damon Doucet, 2011