当前没有测试数据。

2.通讯问题

题目描述

机关$SERN$截获了一条短信。$SERN$总部必须尽快将这个消息通过地下秘密通讯网络，传达到所有分部。

$SERN$共有$N$个部门（总部编号为$0$），通讯网络有$M$条单向通讯线路，每条线路有一个固定的通讯花费$C_i$。消息的传递只能按照固定的方式进行：从一个已知消息的部门向另一个与它有线路相连的部门传递。我们定义总费用为所有部门传递消息的费用和。

幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方法将信息由$X$传递到$Y$，同时能由$Y$传递到$X$），我们就可以忽略它们之间的花费。

$SERN$总部的工程师希望知道，达到目标的最小花费是多少。

输入格式

多组数据，文件以$2$个$0$结尾。

每组数据第一行，一个整数$N$，表示有$N$个包括总部的部门（从$0$开始编号）。然后是一个整数$M$，表示有$M$条单向通讯线路。

接下来$M$行，每行三个整数$X_i$,$Y_i$,$C_i$，表示第$i$条线路从$X_i$连向$Y_i$，花费为$C_i$。

输出格式

每组数据一行，一个整数表示达到目标的最小花费。

数据范围与提示

• 对于$10\%$的数据，保证$M = N - 1$；
• 对于另$30\%$的数据，$1 \leq N \leq 20$，$1 \leq M \leq 20$；
• 对于$100\%$的数据，$1 \leq N \leq 5 \times 10^{4}$，$1 \leq M \leq 10^{5}$，$1 \leq C_i \leq 10^{5}$，$1 \leq$数据组数$\leq 5$。

数据保证一定可以将信息传递到所有部门。

样例

3 3
0 1 100
1 2 50
0 2 100
3 3
0 1 100
1 2 50
2 1 100
2 2
0 1 50
0 1 100
0 0

150
100
50

说明

第一组数据

总部把消息传给分部$1$，分部$1$再传给分部$2$。总费用：$100 + 50 = 150$。

第二组数据

总部把消息传给分部$1$，由于分部$1$和分部$2$可以互相传递消息，所以分部$1$可以无费用把消息传给$2$。总费用：$100 + 0 = 100$。

第三组数据

总部把消息传给分部$1$，最小费用为$50$。总费用：$50$。