描述

你被委派设计一个广域范围内特定点之间的网络连接。给定该区域内的一组点，以及一组可能用于连接点对的电缆铺设路线。对于每一对点之间的每条可能路线，都会给出通过该路线连接这两个点所需的电缆长度。请注意，两个给定点之间可能存在多条可能的路线。假定这些给定的可能路线（直接或间接）连接了该区域内的每两个点。

你的任务是为该区域设计网络，使得每两个点之间都存在（直接或间接）连接（即所有点都相互连通，但不一定通过直接电缆连接），并且所用电缆的总长度最短。

输入

输入文件由若干个数据集组成。每个数据集定义一个所需的网络。数据集的第一行包含两个整数：第一个整数定义给定点的数量$P$，第二个整数定义点之间给定路线的数量$R$。接下来的$R$行定义点之间的给定路线，每行给出三个整数：前两个数字标识点，第三个数字给出路线的长度。数字之间用空格分隔。仅包含一个数字$P = 0$的数据集表示输入结束。数据集之间用空行分隔。

点的最大数量为$50$。给定路线的最大长度为$100$。可能路线的数量没有限制。节点用$1$到$P$（含）之间的整数标识。点$i$和$j$之间的路线可以表示为$i\ j$，也可以表示为$j\ i$ 。

输出

对于每个数据集，在单独的一行上打印一个数字，该数字表示为整个设计网络所用电缆的总长度。

输入数据1

1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

输出数据1

0
17
16
26

来源

2002年东南欧竞赛