Networking

You are asked to design the network connections between certain points in a wide area. You are given a set of points in the area and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable needed to connect the points along that route. Note that there may be many possible routes between two given points. It is assumed that the given routes connect (directly or indirectly) every two points in the area.

Your task is to design the network so that there is a connection (direct or indirect) between every two points -- that is, all points are interconnected, though not necessarily by a direct cable -- while the total length of the cable used is as small as possible.

The input consists of several data sets, each defining one required network. The first line of a data set contains two integers: the number $P$ of points, and the number $R$ of routes between the points. Each of the following $R$ lines defines one route with three integers: the first two identify the two points, and the third gives the length of the route. The numbers are separated by white space. A data set consisting of a single number $P = 0$ marks the end of the input. Data sets are separated by an empty line.

The number of points is at most $50$. The maximum length of a route is $100$. The number of possible routes is unlimited. The points are identified by integers from $1$ to $P$ (inclusive). A route between two points $i$ and $j$ may be given as i j or as j i.

For each data set, print on its own line a single number: the total length of the cable used for the entire designed network.