题目描述

农夫约翰必须给农夫丹送一个包裹，并准备出发去旅行。为了维持和平，他必须给遇到的每一头奶牛一些吃的。当然，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$ 号谷仓。

考虑以下地图：

           [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 必须携带的最少点心数量。

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 

5