题目描述

您被指定在广域中的某些点之间设计网络连接。你得到了一组点在该地区，和一组可能的路线的电缆，可以连接对点。对于两个点之间的每一条可能的路径，你给出了连接该点的电缆的长度。

注意在两个给定点之间可能存在许多可能的路径。据推测，给定的可能的路由连接（直接或间接）在该地区的每两个点。

您的任务是为该区域设计网络，以便在每两个点之间有一个连接（直接或间接） （即所有的点相互连接，但不一定由直接电缆），并且所使用的电缆的总长度是最小的。

输入格式

每个数据集定义一个所需的网络。集合的第一行包含两个整数：第一个定义给定点的数p，第二个给定点之间的给定路径数R。

下面的R线定义给定的点之间的路由，每个给三个整数：前两个数字识别的点，和第三给出的路由的长度。这些数字用空格隔开。

只有一个数字p = 0的数据集表示输入的结束。数据集用空行分隔。

最大点数为50。给定路径的最大长度为100。可能的路线数是无限的。节点被识 别为1和P之间的整数（含）。两个点之间的路线i j或 j i。

输出格式

对于每个数据集，在一个单独的行上打印一个数字，并给出整个设计网络所使用的电缆的总长度。

样例

输入样例

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

输出样例

0
17
16
26