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}$). Между двумя могут быть несколько прямых троп. 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: целые $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