P3020 [USACO11MAR] Package Delivery S

农夫约翰必须给农夫丹送一个包裹，并准备出发去旅行。为了维持和平，他必须给遇到的每一头奶牛一些吃的。当然，FJ很节俭，他想尽可能少遇到奶牛。 FJ 已经绘制了 $N(1 \le N \le 50000)$ 个谷仓的地图，通过 $M(1 \le M \le 50000)$ 条双向牛道连接，每条双向牛道上有 $c[i](0 \le c[i] \le 1000)$ 头奶牛在漫步。每条牛道连接两个不同的谷仓 $a[i]$ 和 $b[i]$（$1 \le a[i] \le N, 1 \le b[i] \le N, a[i] \neq b[i]$）。两个谷仓之间可能由多条牛道直接相连。他目前在 $1$ 号谷仓，农夫丹在 $N$ 号谷仓。 考虑以下地图： ```cpp [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-----[5] 3 ``` 农夫约翰的最佳路线是从 $1 -> 2 -> 4 -> 5 ->$ 6，因为这样他会花费 $1 + 0 + 3 + 1 = 5$ 份点心。 根据 FJ 的地图，考虑到他会给他遇到的每一头不同的奶牛恰好一份点心，他应该携带的最少点心数量是多少？他不在乎路程的长度。

第 $1$ 行：两个空格分隔的整数：$N$ 和 $M$。 第 $2$ 到 $M+1$ 行：每行三个空格分隔的整数：$A_i$ , $B_i$ , $C_i$ 。

一个整数，FJ 必须携带的最少点心数量。